Problem Description

Author: eedwang

Snowdrop收藏著一整排可愛的gura玩偶。 每個玩偶都擁有獨特的能量，當她將它們依序排成一列時，這些能量會彼此產生「共鳴」。

Snowdrop 想知道，在某一段玩偶之間，能量會產生多大的共鳴值。 共鳴值的計算方式如下：

對於從第 L 個到第 R 個玩偶： 第 L 個玩偶的能量乘上 1， 第 L+1 個乘上 2， 依此類推，直到第 r 個玩偶乘上 R−L+1。

r(L,R) = a_L × 1 + a_L+1 × 2 + a_L+2 × 3 + … + a_r × (R-L+1)

給定 Snowdrop 收藏的 n 個玩偶能量值序列： (a₁, a₂, …, a_n)

接著會有 q 次詢問。 每次詢問會給出兩個整數 l 和 r， 請你幫 Snowdrop 計算從第 L 個到第 R 個玩偶之間產生的共鳴值。

Input Format

第一行：一個整數 n，代表玩偶的數量。

第二行：n 個整數 a₁, a₂, …, a_n，分別表示每個玩偶的魔法能量值。

第三行：一個整數 q，代表詢問次數。

接下來的 q 行：每行包含兩個整數 L, R，代表 Snowdrop 想查詢的玩偶區間。

Output Format

對於每個查詢，輸出一行，內容為該區間玩偶的共鳴值。

6
1 1 4 5 1 4
3
1 3
5 6
2 5

15
9
28

Hint

For the first query in the sample input, the answer should be a₁ * 1 + a₂ * 2 + a₃ * 3 = 1 * 1 + 1 * 2 + 4 * 3 = 15. For the second query, the answer should be a₅ * 1 + a₆ * 2 = 1 * 1 + 2 * 4 = 9.

對於範例輸入中的第一個查詢，答案應為 a₁ × 1 + a₂ × 2 + a₃ × 3 = 1 × 1 + 1 × 2 + 4 × 3 = 15。 對於第二個查詢，答案應為 a₅ × 1 + a₆ × 2 = 1 × 1 + 2 × 4 = 9。

範圍: 1 ≤ n ≤ 10⁵ 0 ≤ a_i < 2³², i = 1, 2, ..., n 1 ≤ q ≤ 10⁶ 1 ≤ l ≤ r ≤ n

子任務: Testcase 0~2: n <= 1000 , q ≤ 10⁵ Testcase 3:無額外限制