You are given \(n\) numbers \(a_1, a_2, \ldots, a_n\) together with \(n\) queries. In the \(i\)-th query you are given two integers \(x_i, y_i\) with \(x_i \le y_i\); report the sum of the 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\)).

Unlike the previous task, these test cases are not generated purely at random.

Output

For each query, output a single integer representing the required 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