Thống Kê Lúa Kho Số 5

Mô tả

Cánh đồng mùa nước nổi miền Tây trúng mùa, anh Ba chạy xe chở lúa về kho số năm để tập kết gạo xuất khẩu. Mỗi tháng trong năm, tổ thống kê ghi lại sản lượng lúa thu hoạch tính bằng tấn. Đến cuối năm, ban giám đốc cần tra cứu nhanh: từ tháng $L$ đến tháng $R$ đã thu về tổng cộng bao nhiêu tấn lúa? Do có rất nhiều truy vấn, duyệt từng tháng cho mỗi câu hỏi là quá chậm. Bạn hãy giúp anh Ba lập trình trả lời $Q$ truy vấn nhanh chóng nhé.

Đầu vào

• Dòng đầu chứa số nguyên $n$ — số tháng cần thống kê.
• Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ — sản lượng lúa từng tháng.
• Dòng thứ ba chứa số nguyên $Q$ — 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$ ($1 \le L \le R \le n$) biểu diễn khoảng tháng cần tính tổng.

Đầu ra

• In ra $Q$ dòng, mỗi dòng là tổng sản lượng lúa từ tháng $L$ đến tháng $R$.

Ràng buộc

• $1 \le n \le 10^5$
• $1 \le Q \le 10^5$

Ví dụ

Đầu vào:

6 120 80 150 90 200 60 3 2 4 1 6 3 3

Đầu ra:

320 700 150

Giải thích từng bước: Mảng ban đầu là $[120, 80, 150, 90, 200, 60]$.

• Truy vấn $2$ $4$: tổng từ tháng 2 đến tháng 4 là $80 + 150 + 90 = 320$.
• Truy vấn $1$ $6$: tổng cả sáu tháng là .