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

见题面

见题面