You are given \(n\) numbers \(a_1, a_2, \ldots, a_n\) together with \(n\) queries. The \(i\)-th query provides two integers \(x_i, y_i\) with \(x_i \le y_i\); you must report the sum of all elements whose indices lie between \(x_i\) and \(y_i\) inclusive.

Input

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)).

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(-10^4 \le a_i \le 10^4\)).

Each of the next \(n\) lines contains two integers \(x_i, y_i\) (\(1 \le x_i \le y_i \le n\)).

The test cases are generated by the following program:

#include "testlib.h"
using namespace std;
const int MAX_V = 10000;
const int MIN_V = -MAX_V;
int main(int argc, char* argv[]){
    registerGen(argc, argv, 1);
    int n = atoi(argv[1]);
    cout << n << endl;
    for(int i = 0; i < n; i++) {
        cout << rnd.next(MIN_V, MAX_V);
        if(i + 1 < n) { cout << ' '; }
        else { cout << endl; }
    }
    for(int i = 0; i < n; i++) {
        int x = rnd.next(1, n);
        int y = rnd.next(1, n);
        if(x > y) {
            swap(x, y);
        }
        cout << x << ' ' << y << endl;
    }
    return 0;
}

Output

For each query, output a single integer equal to the requested sum.

Sample Input 1

5
-2493 -7467 2309 -4055 8970
4 5
5 5
2 5
1 3
2 4

Sample Output 1

4915
8970
-243
-7651
-9213