Mountains

문제

There are $NN$ ($1\le N\le 20001\; \backslash leq\; N\; \backslash leq\; 2000$) evenly spaced mountains in a row on the edge of Farmer John's farm. These can be expressed as an array of heights $h_1,h_2,\dots ,h_{N}h\_1,h\_2,\backslash dots,h\_N$. For a mountain $ii$, you can see another mountain $jj$ if there are no mountains strictly higher than the line of sight connecting the tops of mountain $jj$ and $ii$. Formally, for two mountains , they can see each other if there is no $kk$ such that and $(k,h_k)(k,\; h\_k)$ is above the line segment connecting $(i,h_i)(i,\; h\_i)$ and $(j,h_j)(j,\; h\_j)$. There are $QQ$ ($1\le Q\le 20001\; \backslash leq\; Q\; \backslash leq\; 2000$) updates where the height of one mountain increases. Find the total number of unordered pairs of mountains that see each other after each update.

입력

Line $11$ contains $NN$.

Line $22$ contains $NN$ heights $h_1,h_2,\dots ,h_{N}h\_1,h\_2,\backslash dots,h\_N$ (for each $ii$, $0\le h_i\le {10}^{9}0\; \backslash leq\; h\_i\; \backslash leq\; 10^9$).

Line $33$ contains $QQ$.

Lines $44$ to $3+Q3+Q$ contain $xx$, $yy$ ($1\le x\le N1\; \backslash leq\; x\; \backslash leq\; N$, $1\le y1\; \backslash leq\; y$) where $xx$ is the index of the mountain and $yy$ is the amount the height increases by. It is guaranteed that the new height of the mountain is at most ${10}^{9}10^9$.

출력

$QQ$ lines, with the total number of unordered pairs of mountains that see each other after each update.

힌트

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

After the first update, mountain $44$ has a height of $44$, which doesn't block any visibility but does make it so that $44$ can now see $22$, making the new answer $77$.

After the second update, mountain $11$ has a height of $55$, which doesn't block any visibility but does make it so that $11$ can now see $33$, $44$, and $55$, making the new answer $1010$.

After the third update, mountain $33$ has a height of $55$, which blocks mountain $11$ from seeing mountain $44$, blocks mountain $22$ from seeing mountains $44$ and $55$, and doesn't allow itself to see any more mountains since it can already see all of them, making the new answer $77$.

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

7
10
7