Cho \(1\) dãy số \(A\) gồm \(N\) phần tử \(a_1,a_2,...,a_n\).

Yêu cầu

• Hãy cho biết tổng đoạn con từ vị trí \(x\) tới vị trí \(y\) của mảng

Input

• Dòng đầu tiên là độ dài mảng \(N(N \leq 10^6)\).
• Dòng thứ hai gồm \(N\) chữ số \(A_i (A_i \leq 10^6)\).
• Dòng thứ ba là số truy vấn \(Q (Q \leq 10^6)\).
• \(Q\) dòng tiếp theo mỗi dòng gồm 2 số \(x,y (1 \leq x \leq y \leq N)\).

Output

• Gồm nhiều dòng là kết quả bài toán.

6
1 2 3 2 1 2
3
1 3
2 4
1 6

6
7
11