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

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 <= 10^6)\).
• Dòng thứ hai gồm \(N\) chữ số \(A_i\) \((A_i <= 10^6)\).
• Dòng thứ ba là số truy vấn \(Q\) \((Q <= 10^6)\).
• \(Q\) dòng tiếp theo mỗi dòng gồm 2 số \(x\), \(y\), \((x, y <= 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