Cho một dãy số nguyên gồm N phần tử ~a_1,a_2,…,a_N~

Yêu cầu:

Cho hai chỉ số ~L,R~ (~1≤L≤R≤N~). Hãy tính ~ f(L,R) = a_L + a_L+1 + ... + a_R~

Input

-Dòng đầu gồm duy nhất một số nguyên dương ~N~ (~N≤10^5 ~);

-Dòng thứ hai gồm ~N~ số nguyên ~a_1,a_2,…,a_N~ (|~a_i~ | ≤ ~10^9~ );

-Dòng thứ ba gồm một số nguyên dương ~T~- số lượng testcase (~T≤10^5~ );

-~T~ dòng tiếp, mỗi dòng gồm một cặp số nguyên dương ~L,R~ (~1≤L≤R≤N~).

Output

In ra ~T~ dòng, mỗi dòng là ~f(L,R)~ tương ứng.

Ví dụ:

input

5

8 2 -4 3 1

3

1 3

4 4

3 5

output ```

6

3

0