Cerința

Fie N un numar natural și un șir de N numere naturale V[1], V[2], …, V[N]. Pentru M întrebări de forma (i,j), să se calculeze suma termenilor V[i], V[i + 1], …, V[j].

Date de intrare

Pe prima linie a fișierului sume2.in se găsește un număr natural N. Pe urmatoarea linie sunt N numere naturale, reprezentând valorile șirului V. Pe a treia linie se găsește un număr natural M reprezentând numărul de întrebări, iar pe următoarele M linii câte o pereche de numere (i,j), reprezentând o întrebare pentru care se cere să se calculeze suma V[i] + V[i + 1] + ... + V[j].

Date de ieșire

Pe prima linie din fişierul sume2.out se găseşte răspunsul la prima întrebare din fişierul de intrare, pe a doua linie se găseşte răspunsul la cea de-a doua întrebare, și așa mai departe.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• 1 ≤ M ≤ 500.000
• 0 ≤ V[i] ≤ 1.000.000.000
• Pentru 30% dintre teste N, M ≤ 1.000

Exemplu

sume2.in

4
1 2 3 4  
2
1 3
2 4

sume2.out

6
9

Explicație

Suma elementelor de pe pozițiile de la 1 la 3 este 6.
Suma elementelor de pe pozițiile de la 2 la 4 este 9.

#include <bits/stdc++.h>
using namespace std;
ifstream cin("sume2.in");
ofstream cout("sume2.out");
int main()
{
    long long n , m , x , y , a[100001] , s[100001]={0};
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
    {
        cin >> a[i];
        s[i]=s[i-1]+a[i];
    }
    cin >> m;
    for(int i = 0 ; i < m ; ++i)
    {
        cin >> x >> y;
        cout << s[y]-s[x - 1] << endl;
    }
}