Giao Động Nhiệt Nước Biển Vũng Tàu

Mô tả

Phòng Kinh tế Vũng Tàu đặt trạm quan trắc nhiệt độ nước biển dọc bãi Sau. Mỗi ngày kỹ thuật viên ghi lại mức chênh lệch nhiệt so với ngày hôm trước (gọi là giao động nhiệt), tạo thành một dãy $n$ phần tử nguyên. Để báo cáo định kỳ, giám đốc yêu cầu tính tổng giao động nhiệt trên nhiều đoạn tuần khác nhau — mỗi đoạn được cho bởi chỉ số bắt đầu và kết thúc.

Việc tính trực tiếp cho từng đoạn sẽ rất chậm khi số lượng truy vấn lớn, nên bạn cần tiền xử lý để trả lời mỗi truy vấn nhanh chóng.

Đầu vào

• Dòng đầu chứa số nguyên $n$ — số lượng ngày quan trắc ($1 \le n \le 10^5$).
• Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ — giao động nhiệt từng ngày ().
• Dòng thứ ba chứa số nguyên $q$ — số lượng truy vấn ($1 \le q \le 10^5$).
• $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$) — chỉ số bắt đầu và kết thúc của đoạn (đánh số từ 1).

Đầu ra

• $q$ dòng, mỗi dòng là một số nguyên — tổng giao động nhiệt trên đoạn $[l, r]$ tương ứng.

Ràng buộc

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

Ví dụ

Input:

5 3 -1 4 2 -5 3 1 3 2 5 4 4

Output:

6 0 2

Giải thích:

Dãy giao động: [3, -1, 4, 2, -5].

• Truy vấn 1 3: tính $3 + (-1) + 4 = 6$.
• Truy vấn 2 5: tính $(-1) + 4 + 2 + (-5) = 0$.