Cho một mảng a có ~N~ phần tử và ~Q~ truy vấn. Mỗi truy vấn sẽ cho 2 số ~x~ và ~y~, bạn sẽ phải cho biết tổng ~a[x] + a[x+1] + a[x+2] + ... + a[y]~ bằng bao nhiêu.

Input:

• Dòng đầu chứa số ~N~.
• Dòng thứ 2 chứa ~N~ số, là miêu tả mảng ~a~.
• Dòng thứ 3 chứa số ~Q~.
• ~Q~ dòng sau, mỗi dòng chứa 2 số ~x~ và ~y~.

Output:

• Gồm ~Q~ dòng, mỗi dòng chứa số nguyên là tổng các phần tử từ ~x~ đến ~y~ tương ứng.

Example:

Input:

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

Output:

6
7
11

Constraints:

~N \le 10^5 ; a[i] \le 10^9 ; Q \le 10^5; 1 \le x \le y \le N~