Tổng đoạn liên tục nhau

Cho dãy số nguyên \(a = (a_1, a_2, \ldots, a_n)\). Hãy trả lời \(T\) truy vấn, mỗi truy vấn yêu cầu tính tổng các phần tử liên tiếp \(a_l + a_{l+1} + \cdots + a_r\).

Input

• Dòng đầu ghi số nguyên dương \(n\).
• Dòng thứ hai ghi \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(|a_i| \le 10^9\)), các số cách nhau một dấu cách.
• Dòng thứ ba ghi số nguyên dương \(T\) là số lượng đoạn cần tính.
• Trong \(T\) dòng tiếp theo, mỗi dòng ghi hai số nguyên dương \(l\) và \(r\) (\(1 \le l \le r \le n\)) cách nhau một dấu cách.

Output

Gồm \(T\) dòng, mỗi dòng ghi một số nguyên là tổng tương ứng tìm được.

Scoring

• \(50\%\) số điểm: \(1 \le n, T \le 1000\).
• \(50\%\) số điểm: \(1000 < n, T \le 200\,000\).

Sample Input 1

6
4 5 -9 2 -6 1
2
1 4
2 5

Sample Output 1

2
-8