[USACO22DEC] Mountains G

题目描述

沿着 Farmer John 的农场边缘有 $N(1 \le N \le 2000)$ 座排成一行等间隔分布的山。这些山可以用一个高度数组 $h_1,h_2, \cdots ,h_N$ 表示。对于山 $i$,如果没有一座山严格高于连接山 $j$ 和 $i$ 山顶的视线,则可以看到山 $j$。形式化地说,对于两座山 $i<j$,如果不存在 $k$ 使得 $i<k<j$ 并且 $(k,h_k)$ 高于连接 $(i,h_i)$ 和 $(j,h_j)$ 的线段,则这两座山之间互相可以看到对方。给定 $Q(1 \le Q \le 2000)$ 次更新操作,每次更新增加一座山的高度。求每次更新后可以互相看到的山的无序对数。

输入输出格式

输入格式


输入的第一行包含 $N$。 第 $2$ 行包含 $N$ 个高度 $h_1,h_2,\cdots,h_N$(对每一个 $i$,有 $0 \le h_i \le 10^9$)。 第 $3$ 行包含 $Q$。 第 $4$ 到 $3+Q$ 行每行包含 $x,y(1 \le x \le N,1 \le y)$,其中 $x$ 为山的编号,$y$ 是山增加的高度。输入保证这座山更新后的高度不超过 $10^9$。

输出格式


输出 $Q$ 行,包含每次更新后可以互相看到的山的无序对数。

输入输出样例

输入样例 #1

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

输出样例 #1

7
10
7

说明

### 样例 1 解释 初始时,以下的山之间可以互相看到:$(1,2)$,$(2,3)$,$(2,5)$,$(3,4)$,$(3,5)$,$(4,5)$,共 $6$ 对。 第一次更新后,山 $4$ 的高度为 $4$,这不会阻挡现有的可见性,但使得山 $4$ 现在可以看到山 $2$,从而使得答案变为 $7$。 第二次更新后,山 $1$ 的高度为 $5$,这不会阻挡现有的可见性,但使得山 $1$ 现在可以看到山 $3$,$4$ 和 $5$,从而使得答案变为 $10$。 第三次更新后,山 $3$ 的高度为 $5$,阻挡了山 $1$ 看到山 $4$,阻挡了山 $2$ 看到山 $4$ 和 $5$,同时由于该山本就可以看到其他所有山,所以并没有使得该山看到更多的山,从而使得答案变为 $7$。 ### 测试点性质 - 测试点 $2-5$ 满足 $N,Q \le 100$。 - 测试点 $6-11$ 满足 $Q \le 10$。 - 测试点 $12-21$ 没有额外性质。