Cerința

Se dă un vector A cu N numere naturale. Pentru Q întrebări de forma (x, y) aflați rezultatul sumei A[x] + 2 * A[x + 1] + ... + (y - x + 1) * A[y].

Date de intrare

Fișierul de intrare qtsume.in conține pe prima linie numărul N, iar pe a doua linie N numere naturale separate prin spații, reprezentând vectorul A. Pe următoarea linie se află numărul Q. Urmează Q linii, pe fiecare linie se află două numere naturale separate printr-un spațiu reprezentând x și y.

Date de ieșire

Fișierul de ieșire qtsume.out va conține pe Q linii, pe linia i aflându-se răspunsul la a i-a întrebare în ordinea citirii.

Restricții și precizări

• 1 ≤ N, Q ≤ 100.000
• 1 ≤ A[i] ≤ 1.000.000
• 1 ≤ x ≤ y ≤ N

Exemplu:

qtsume.in

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

qtsume.out

5
48
14

Explicație

Pentru a 3-a întrebare avem A[2] + 2 * A[3] + 3 * A[4] = 1 + 2 * 2 + 3 * 3 = 14