Problem 2. Mountains

USACO 2022 December Contest, Gold

Note: the time limit for this problem is 5s, 2.5 times the default. The memory limit is twice the default.

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.

INPUT FORMAT (input arrives from the terminal / stdin):

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$.

OUTPUT FORMAT (print output to the terminal / stdout):

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

SAMPLE INPUT:

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

SAMPLE OUTPUT:

7
10
7

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$.

SCORING: Tests 2-5 satisfy $N, Q\le 100$. Tests 6-11 satisfy $Q \leq 10$. Tests 12-21 have no additional constraints.

Problem credits: Joe Li and Larry Xing