Những Ngọn Núi

Có $N$ ngọn núi đặt cách đều nhau trên một đường thẳng. Ngọn núi thứ $i$ có đỉnh tại điểm $(i,h_i)$.

Hai ngọn núi $i$ và $j$ ($i<j$) nhìn thấy nhau nếu không có ngọn núi $k$ nào với $i<k<j$ mà đỉnh của nó nằm hoàn toàn phía trên đoạn thẳng nối đỉnh núi $i$ với đỉnh núi $j$. Một đỉnh nằm đúng trên đoạn thẳng đó thì không che khuất tầm nhìn.

Có $Q$ lần cập nhật, mỗi lần tăng độ cao của một ngọn núi. Sau mỗi lần cập nhật, 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$.
• Dòng 2: $N$ số nguyên $h_1,h_2,\dots ,h_N$.
• Dòng 3: số nguyên $Q$.
• $Q$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $x$ và $y$, nghĩa là tăng $h_x$ thêm $y$. Các cập nhật được áp dụng lần lượt và có hiệu lực với những cập nhật sau đó.

Dữ liệu ra

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

Ràng buộc

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

Ví dụ