Problem 2. Mountains

USACO 2022 December Contest, Gold

注意：本题的时间限制为 5 秒，通常限制的 2.5 倍。内存限制是通常限制的两倍。

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

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $N$。

第 $2$ 行包含 $N$ 个高度 $h_1,h_2,\dots,h_N$（对每一个 $i$，有 $0 \leq h_i \leq 10^9$）。

第 $3$ 行包含 $Q$。

第 $4$ 到 $3+Q$ 行每行包含 $x$，$y$（$1 \leq x \leq N$，$1 \leq y$），其中 $x$ 为山的编号，$y$ 是山增加的高度。输入保证这座山更新后的高度不超过 $10^9$。

输出格式（输出至终端 / 标准输出）：

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

输入样例：

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

输出样例：

7
10
7

初始时，以下的山之间可以互相看到：$(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 \leq 10$。 测试点 12-21 没有额外性质。

供题：Joe Li，Larry Xing