문제

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.

입력

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.

예제 입력 1

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

예제 출력 1

7
10
7

점수

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