Những Ngọn Núi

Có $N$ ngọn núi đặt cách đều nhau với độ cao $h_1,h_2,\dots ,h_N$. Hai ngọn núi $i$ và $j$ ($i<j$) có thể nhìn thấy nhau nếu không có ngọn núi $k$ nào ($i<k<j$) nằm phía trên đoạn thẳng nối đỉnh hai ngọn núi.

Sau mỗi trong $Q$ lần cập nhật (tăng độ cao một ngọn núi), hãy đếm số cặp ngọn núi nhìn thấy nhau.

Dữ liệu vào

• Dòng 1: số nguyên $N$ ($1\le N\le 2000$).
• Dòng 2: $N$ số nguyên $h_1,\dots ,h_N$ ($0\le h_i\le {10}^9$).
• Dòng 3: số nguyên $Q$ ($1\le Q\le 2000$).
• $Q$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $x$ và $y$ ($1\le x\le N$, $1\le y$) — tăng $h_x$ thêm $y$.

Dữ liệu ra

In $Q$ dòng, mỗi dòng chứa số cặp ngọn núi nhìn thấy nhau sau lần cập nhật tương ứng.

Ràng buộc

• $N,Q\le 2000$
• $0\le h_i\le {10}^9$

Ví dụ