Cho dãy số nguyên \(a\) gồm \(n\) phần tử \(a_1,a_2,...,a_n\) và \(Q\) truy vấn.

Mỗi truy vấn là một cặp số nguyên dương \((L, R)\), hãy in ra tổng đoạn con từ \(a_L\) đến \(a_R\).

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng 2 chứa \(n\) số nguyên mô tả dãy \(a\).
• Dòng 3 chứa số nguyên dương \(Q\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa cặp số nguyên \(L, R(L\leq R\leq n)\).

Output

• Gồm \(Q\) dòng, mỗi dòng là tổng đoạn con cần tìm.

Constraints

• \(n\leq 10^5\)
• \(|a_i|\leq 100\)
• \(Q\leq 10^5\)

Example