Cho một mảng số nguyên a gồm n phần tử (~0 < n \leq 10^5~). Có q câu hỏi yêu cầu em hãy tính tổng mảng a từ vị trí thứ l đến vị trí r (~0< l \leq r \leq 10^5~)

Dữ liệu vào

• Dòng 1 gồm 1 số nguyên dương n

• Dòng 2 gồm n số nguyên của a[1], a[2], a[3],..., a[n]

• Dòng 3 gồm 1 số nguyên dương ~q (q \le 10^5)~

• q dòng tiếp theo, mỗi dòng gồm hai số l và r là câu hỏi mà bạn cần trả lời

Kết quả

• Gồm q dòng, mỗi dòng là một câu trả lời tương ứng với q câu hỏi

INPUT

5

5 8 9 1 3

2

1 2

2 3

OUTPUT

13

17