Lưu ý: Giới hạn thời gian là 5s. Giới hạn bộ nhớ là 512MB

Có \(N\) ngọn núi \((1 \le N \le 2000)\) được đặt cách nhau trên cùng một dãy núi của nông dân John. Các ngọn núi này được thể hiện bởi một dãy độ cao \(h_1, h_2, \dots, h_n\). Đứng ở ngoại núi thứ \(i\), bạn có thể nhìn thấy ngọn núi thứ \(j\) nếu như không có ngọn núi nào cắt đường chéo nối bởi đỉnh của ngọn núi \(i\) và đỉnh của ngọn núi \(j\). Nói cách khác, với hai ngọn núi \(i < j\) có thể nhìn thấy nhau nếu không tồn tại ngọn núi \(k\) thoả mãn \(i < k < j\) và điểm \((k, h_k)\) nằm bên trên đoạn thẳng tạo bởi hai điểm \((i, h_i)\) và \((j, h_j)\). Có \(Q\) \((1 \le Q \le 2000)\) lần cập nhật độ cao, trong đó, mỗi lần cập nhật sẽ làm tăng cao của một ngọn núi. Tìm tổng số lượng các cặp có thể nhìn thấy nhau sau mỗi lần cập nhật (Cặp \((i, j)\) và \((j, i)\) được coi là như nhau).

Input

• Dòng \(1\) là số \(N\).
• Dòng \(2\) là \(N\) số \(h_1, h_2, \dots, h_n\) (\(\forall i, 0 \le h_i \le 10^9\)).
• Dòng \(3\) là số \(Q\).
• Từ dòng \(4\) đến dòng \(Q + 3\), mỗi dòng gồm \(2\) số \(x\) và \(y\) \((1 \le x \le N, 1 \le y)\), trong đó \(x\) là vị trí của ngọn núi sẽ thay đổi độ cao và \(y\) là lượng mà độ cao của ngọn núi này tăng thêm \((h_x = h_x + y)\). Dữ liệu đảm bảo độ cao mới của ngọn núi không vượt quá \(10^9\).

Output

• \(Q\) dòng, mỗi dòng là số lượng các cặp thoả mãn đề bài.

Scoring

• Subtask \(1\): \(N, Q \le 100\).
• Subtask \(2\): \(Q \le 10\).
• Subtask \(3\): Không có thêm ràng buộc.

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

7
10
7