【题目描述】

在一个竖直的平面直角坐标系中，N 头牛站在 x 轴上，第 i 头牛所站位置的 x 坐标恰好为 i，身高为 h_i。

我们认为这些牛的眼睛长在头顶上，即牛 i 的眼睛的坐标为 (i, h_i)。

对于两头牛 i 和 j，不妨假设 i < j ，如果两头牛之间存在一头牛 k 挡住了它们的视线，即存在一个 k 满足 i < k < j 并且 h_k 高于连接 (i,h_i) 和 (j,h_j) 的线段，则这两头牛互相看不见对方，否则，如果不存在这样的牛 k，则两头牛就可以互相看见。

现在给定 M 次操作，每次操作增加一头牛的身高，求每次操作后可以互相看见的牛的对数。

【输入格式】

第 1 行包含一个整数 N。

第 2 行包含 N 个整数 h_1,h_2,……,h_N。

第 3 行包含一个整数 M。

接下来 M 行，每行包含两个整数 p, q，其中 p 表示牛的编号，q 表示使得牛 p 增加的高度。

【输出格式】

M 行，每次操作后的答案占一行。

【样例输入】

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，使得 {2,4} 可以互相看见，其他互相可见的牛没有影响，答案变为 7。

第二次操作后，牛 1 的身高变为 5，使得牛 1 可以看见牛 3，4 和 5，其他互相可见的牛没有影响，答案变为 10。

第三次操作后，牛 3 的身高变为 5，挡住了 {1,4}，{2,4}，{2,5} 三对牛的视线，其他互相可见的牛没有影响，答案变为 7。

【数据范围】

全部数据满足 0 ≤ h_i ≤ 10^9, 1 ≤ p ≤ N, 1 ≤ q ≤ 2^30, 且输入保证每次更新后的牛的身高不超过 2^30。

其中有 20%的测试点满足 1 ≤ N ≤ 100, 1 ≤ M ≤ 100。

其中有 30%的测试点满足 1 ≤ N ≤ 2000, 1 ≤ M ≤ 10。

其中有 50%的测试点满足 1 ≤ N ≤ 2000, 1 ≤ M ≤ 2000。