Cho dãy số ~A~ gồm ~N~ phần tử.

Có ~Q~ truy vấn, mỗi truy vấn gồm hai chỉ số ~l~ và ~r~. Nhiệm vụ của bạn là tính tổng các phần tử trong đoạn từ vị trí ~l~ đến vị trí ~r~.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~N~.
• Dòng thứ hai chứa ~N~ số nguyên ~A_i~.
• Dòng tiếp theo chứa số nguyên ~Q~, là số lượng truy vấn.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l~ và ~r~.

Ràng buộc

• ~1 ≤ N ≤ 10^6~.
• ~1 ≤ A_i ≤ 10^9~.
• ~1 ≤ Q ≤ 1000~.
• ~1 ≤ l ≤ r ≤ N~.

Kết quả

Với mỗi truy vấn, in ra tổng các phần tử trong đoạn ~[l, r]~ trên một dòng.

Ví dụ

Dữ liệu vào

5
1 2 3 4 5
1
1 3

Kết quả

6

Giải thích

Truy vấn yêu cầu tính tổng các phần tử từ vị trí ~1~ đến vị trí ~3~:

~1 + 2 + 3 = 6~.