Courses

データ構造

プレフィックスの合計

Module: プレフィックスの合計

Problem

6 /8

ギャング・オブ・フォミン No.2

Problem

フォミンのギャングは n 個のグループで構成され、各グループには a_i 人がいます。 q 襲撃が計画されています。 i 番目の襲撃には、セグメント \([l_i, r_i]\).

メレホフは悲しいので、襲撃ごとに可能なユニットの数を \(10^9 + 7\) を法として計算することにしました。しかし、グレゴリーは常に人生の意味を考え、真実を探し求めているため、計算に集中できず、あなたに助けを求めます。

入力
最初の行には数値 n (\(1 <= n <= 10^5\)) – が含まれています。フォミン一味のグループ数.
2 行目には n 個の自然数 a_i (\(1 <= a_i < = 10^6\)) – i 番目のグループの人数。
3 行目には q – という数字が含まれています。襲撃の数。
以下は q 行で、それぞれに 2 つの数字が含まれています – l_i と r_i (\(1 <= l_i <= r_i <= n\)) – i-th raidに参加しているグループの数。

インプリント
q の数字を 1 行に 1 つずつ表示 –タスクへの応答。