Problem Description

Along the edge of Farmer John’s farm, there are $N(1 \le N \le 2000)$ mountains arranged in a line at equal spacing. These mountains can be represented by a height array $h_1,h_2,\cdots,h_N$. For mountain $i$, mountain $j$ is visible if there is no mountain strictly higher than the line of sight connecting the peaks of mountains $j$ and $i$. Formally, for two mountains $i<j$, if there does not exist $k$ such that $i<k<j$ and the point $(k,h_k)$ is above the line segment connecting $(i,h_i)$ and $(j,h_j)$, then these two mountains can see each other.

You are given $Q(1 \le Q \le 2000)$ update operations, each of which increases the height of one mountain. After each update, output the number of unordered pairs of mountains that can see each other.

Input Format

The first line contains $N$.

The second line contains $N$ heights $h_1,h_2,\cdots,h_N$ (for each $i$, $0 \le h_i \le 10^9$).

The third line contains $Q$.

Lines $4$ to $3+Q$ each contain $x,y(1 \le x \le N,1 \le y)$, where $x$ is the index of the mountain and $y$ is the amount by which its height increases. The input guarantees that the height of this mountain after the update does not exceed $10^9$.

Output Format

Output $Q$ lines, each containing the number of unordered pairs of mountains that can see each other after the corresponding update.

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

7
10
7

Hint

Sample 1 Explanation

Initially, the following pairs of mountains can see each other: $(1,2)$, $(2,3)$, $(2,5)$, $(3,4)$, $(3,5)$, $(4,5)$, for a total of $6$ pairs.

After the first update, the height of mountain $4$ becomes $4$. This does not block any existing visibility, but it makes mountain $4$ able to see mountain $2$, so the answer becomes $7$.

After the second update, the height of mountain $1$ becomes $5$. This does not block any existing visibility, but it makes mountain $1$ able to see mountains $3$, $4$, and $5$, so the answer becomes $10$.

After the third update, the height of mountain $3$ becomes $5$. This blocks mountain $1$ from seeing mountain $4$, and blocks mountain $2$ from seeing mountains $4$ and $5$. At the same time, since this mountain could already see all other mountains, it does not make it see more mountains, so the answer becomes $7$.

Test Point Properties

• Test points $2-5$ satisfy $N,Q \le 100$.
• Test points $6-11$ satisfy $Q \le 10$.
• Test points $12-21$ have no additional properties.

Translated by ChatGPT 5