Cho dãy số nguyên \(a_1\), \(a_2\), \(a_3\), ... \(a_n\) và một số cặp \(i, j \in [1;n]\) với \(i < j\). Viết chương trình tính và in ra các giá trị tổng \(a_i + a_{i+1} + a_{i+2} + ... + a_j\) tương ứng.

Input Specification

Gồm nhiều dòng:

• Dòng đầu tiên chứa số nguyên dương \(n\)
• Dòng thứ hai chứa dãy \(n\) số nguyên
• Dòng thứ ba chứa số nguyên dương T - là số trường hợp cần tính.
• Mỗi dòng trong T dòng tiếp theo chứa một cặp số \(i, j\).

Output Specification

In ra mỗi kết quả trên một dòng theo thứ tự tương ứng.

Constraints

• \(n \leq 10^6\)
• \(|a_i| \leq 10^3\)
• \(T \leq 5 \times 10^5\)

Input Sample

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

Output Sample

5
10