Tổng nhiều đoạn

Bối cảnh

Một hệ thống có cùng một dãy số nhưng phải trả lời nhiều truy vấn tổng đoạn. Nếu mỗi truy vấn cộng lại từ đầu, công việc bị lặp.

Prefix sum cho phép chuẩn bị một mảng tích lũy rồi trả lời mỗi truy vấn nhanh.

Yêu cầu

1. Đọc n và mảng.
2. Xây prefix[k] là tổng k phần tử đầu tiên.
3. Đọc q truy vấn L R (0-based, inclusive).
4. In tổng a[L] + ... + a[R] cho từng truy vấn.

Input

Dòng 1: n. Dòng 2: n số. Dòng 3: q. q dòng tiếp theo: L R.

Output

q dòng tổng đoạn.

Ràng buộc

1 ≤ n,q ≤ 5000, |a[i]| ≤ 10^9.

Ví dụ 1

Input

5
1 2 3 4 5
3
0 4
1 3
2 2

Output

15
9
3

Giải thích

Tổng toàn dãy là 15. Đoạn 1..3 có 2+3+4=9. Đoạn 2..2 chỉ có giá trị 3.

Ví dụ 2

Input

4
-1 -2 -3 -4
2
0 1
2 3

Output

-3
-7

Giải thích

Hai đoạn là [-1,-2] có tổng -3 và [-3,-4] có tổng -7.

Thông tin học tập

• Module: M03
• Buổi: B10
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: prefix sums, range queries, static arrays
• Giới hạn kiến thức: B01-B10
• Time limit: 2 second(s)
• Memory limit: 256 MB
• Point: 100