TANGDOAN Tăng đoạn

TANGDOAN Tăng đoạn

Cho dãy n số nguyên a[1], a[2], …, a[n]. Ta thực hiện p truy vấn loại 1, mỗi truy vấn có dạng x y sẽ tăng các phần tử trong đoạn a[x], a[x+1], …, a[y] lên 1 đơn vị. Sau đó ta thực hiện q truy vấn loại 2, mỗi truy vấn có dạng x y sẽ cho biết tổng các số trong đoạn a[x], a[x+1], …, a[y]

Input

·        Dòng đầu ghi số nguyên dương n (1 ≤ n ≤ 10⁵)

·        Dòng thứ hai ghi n số nguyên a[1], a[2], …, a[n] (|a[i]| ≤ 10⁶)

·        Dòng thứ ba ghi số nguyên dương p (1 ≤ p ≤ 10⁵)

·        p dòng tiếp theo, mỗi dòng ghi 2 số x y là thông tin 1 truy vấn loại 1 (1 ≤ x ≤ y ≤ n)

·        Dòng tiếp theo ghi số nguyên dương q (1 ≤ q ≤ 10⁵)

·        q dòng tiếp theo, mỗi dòng ghi 2 số x y là thông tin 1 truy vấn loại 2. (1 ≤ x ≤ y ≤ n)

Output: Ghi q dòng, mỗi dòng là kết quả 1 truy vấn loại 2 theo thứ tự

Input	Output	Giải thích
5 3 -2 1 4 2 2 1 5 2 4 2 2 5 3 4	12 9	Sau truy vấn loại 1 (1,5), dãy là: 4 -1 2 5 3 Sau truy vấn loại 1 (2,4), dãy là: 4 0 3 6 3 Kết quả truy vấn loại 2 (2,5) là 4 + 0 + 3 + 6 + 3 = 12 Kết quả truy vấn loại 2 (3,4) là 3 + 6 = 9