26970번 - Mountains 다국어

문제

There are $N$ (1ドル \leq N \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$. For a mountain $i,ドル you can see another mountain $j$ if there are no mountains strictly higher than the line of sight connecting the tops of mountain $j$ and $i$. Formally, for two mountains $i < j,ドル they can see each other if there is no $k$ such that $i < k < j$ and $(k, h_k)$ is above the line segment connecting $(i, h_i)$ and $(j, h_j)$. There are $Q$ (1ドル \leq Q \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 1ドル$ contains $N$.

Line 2ドル$ contains $N$ heights $h_1,h_2,\dots,h_N$ (for each $i,ドル 0ドル \leq h_i \leq 10^9$).

Line 3ドル$ contains $Q$.

Lines 4ドル$ to 3ドル+Q$ contain $x,ドル $y$ (1ドル \leq x \leq N,ドル 1ドル \leq y$) where $x$ is the index of the mountain and $y$ is the amount the height increases by. It is guaranteed that the new height of the mountain is at most 10ドル^9$.

출력

$Q$ 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),ドル $(2, 3),ドル $(2, 5),ドル $(3, 4),ドル $(3, 5),ドル $(4, 5),ドル a total of 6ドル$.

After the first update, mountain 4ドル$ has a height of 4ドル,ドル which doesn't block any visibility but does make it so that 4ドル$ can now see 2ドル,ドル making the new answer 7ドル$.

After the second update, mountain 1ドル$ has a height of 5ドル,ドル which doesn't block any visibility but does make it so that 1ドル$ can now see 3ドル,ドル 4ドル,ドル and 5ドル,ドル making the new answer 10ドル$.

After the third update, mountain 3ドル$ has a height of 5ドル,ドル which blocks mountain 1ドル$ from seeing mountain 4ドル,ドル blocks mountain 2ドル$ from seeing mountains 4ドル$ and 5ドル,ドル and doesn't allow itself to see any more mountains since it can already see all of them, making the new answer 7ドル$.