该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P8904 [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

输入 #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$ 没有额外性质。