Loli là một lập trình viên về game. Công ty của Loli đang làm một con game AAA rất căng, họ tự tin con game cưng này sẽ đạt được Game Of The Year 2050, là một gương mặt sừng sỏ thay đổi ngành công nghiệp giải trí.

Loli được giao code một phân đoạn của game. Bối cảnh phân đoạn trong trò chơi là một nửa quả đồi, được chia thành ~n~ cột. Độ cao của cột ~i~ là ~h_i~ ~(0 \le h_1 \le h_2 \le \dots \le h_n \le 10^9)~. Người chơi sẽ thực hiện ~m~ hành động theo trình tự, mỗi hành động được đặc trưng bởi hai số ~(i, L)~, có nghĩa là nhân vật hiện tại ở cột ~i~ bắn một tia độ dài ~L~ về bên phải. Khi nhân vật ở cột ~i~ bắn một tia độ dài ~L~ về bên phải, các cột ~i + 1, i + 2, \dots, i + L~ sẽ bị giảm độ cao về bằng với độ cao hiện tại của cột ~i~.

Điểm của mỗi hành động là số lượng đất bị phá, tức là tổng mức giảm độ cao của các cột bị giảm. Công ty muốn Loli tính điểm được cộng thêm sau khi người chơi thực hiện xong mỗi một hành động.

Input

• Dòng đầu chứa một số nguyên ~n~ ~(1\le n \le 10^5)~.
• Dòng tiếp theo chứa dãy ~h_1, h_2, \dots, h_n~ là độ cao từng cột của đồi ~(0 \le h_1 \le h_2 \le \dots \le h_n \le 10^9)~.
• Dòng tiếp theo chứa số lượt chơi ~m~ ~(1\le m \le 10^5)~.
• ~m~ dòng tiếp theo mỗi dòng chứa một hành động, có dạng: ~i\ L~ ~(1 ≤ L ≤ n - i)~.

Output

• In ra trên ~m~ dòng là điểm được cộng thêm của ~m~ hành động.

Subtask

• Subtask 1 (~40\%~ điểm): ~n, m \le 5000~.
• Subtask 2 (~60\%~ điểm): Không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

1
3
6
0

Giải thích

• Dãy đang có độ cao lần lượt là ~[1,2,3,4,5]~.
• Sau hành động đầu tiên, ta có độ cao của cột ~4~ được san bằng với cột ~3~, dãy mới là ~[1,2,3,3,5]~, chênh lệch tổng 1 đơn vị.
• Sau hành động thứ hai, ta có độ cao của cột ~2,3~ được san bằng với cột ~1~, dãy mới là ~[1,1,1,3,5]~, chênh lệch tổng 3 đơn vị.
• Sau hành động thứ ba, ta có độ cao của cột ~4,5~ được san bằng với cột ~3~, dãy mới là ~[1,1,1,1,1]~, chênh lệch tổng 6 đơn vị.
• Sau hành động thứ tư, ta có độ cao của cột ~2,3,4,5~ được san bằng với cột ~1~, dãy mới là ~[1,1,1,1,1]~, không đổi.