Tổng nhiều đoạn bằng prefix

Bối cảnh

Một dãy tĩnh có nhiều truy vấn tổng đoạn [L,R] theo index 0-based.

Prefix pre[i+1]=pre[i]+a[i] làm mỗi truy vấn O(1).

Yêu cầu

1. Build pre có n+1 phần tử.
2. Mỗi query [L,R] in pre[R+1]-pre[L].

Input

Dòng 1 n; dòng 2 n số; dòng 3 q; q dòng L R 0-based.

Output

q dòng tổng.

Ràng buộc

1≤n,q≤5000, 0≤L≤R<n, |a[i]|≤10^9.

Ví dụ 1

Input

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

Output

1
15
9
5

Giải thích

Prefix dùng convention pre[i+1]=pre[i]+a[i], nên với dãy 1 2 3 4 5 ta có prefix 0,1,3,6,10,15. Query [0,4] lấy pre[5]-pre[0]=15; [1,3] lấy pre[4]-pre[1]=10-1=9. Hai query một phần tử [0,0] và [4,4] lần lượt cho 1 và 5. Vì vậy các output là 1,15,9,5.

Ví dụ 2

Input

1
7
2
0 0
0 0

Output

7
7

Giải thích

Dãy chỉ có một phần tử 7 nên prefix là 0,7. Cả hai query đều là [0,0], công thức pre[1]-pre[0] luôn cho 7. Ví dụ xác nhận convention n+1 xử lý L=0 mà không cần nhánh đặc biệt.

Thông tin học tập

• Module: M05
• Buổi: B17
• Loại bài: LAB
• Độ khó: Medium
• Concepts: prefix sum, n+1, range sum, long long
• Giới hạn kiến thức: B01-B17
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100