{"raw_statement":[{"iden":"statement","content":"沿着 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)$ 次更新操作，每次更新增加一座山的高度。求每次更新后可以互相看到的山的无序对数。 "},{"iden":"input","content":"输入的第一行包含 $N$。\n\n第 $2$ 行包含 $N$ 个高度 $h_1,h_2,\\cdots,h_N$（对每一个 $i$，有 $0 \\le h_i \\le 10^9$）。\n\n第 $3$ 行包含 $Q$。\n\n第 $4$ 到 $3+Q$ 行每行包含 $x,y(1 \\le x \\le N,1 \\le y)$，其中 $x$ 为山的编号，$y$ 是山增加的高度。输入保证这座山更新后的高度不超过 $10^9$。 "},{"iden":"output","content":"输出 $Q$ 行，包含每次更新后可以互相看到的山的无序对数。 "},{"iden":"note","content":"### 样例 1 解释\n\n初始时，以下的山之间可以互相看到：$(1,2)$，$(2,3)$，$(2,5)$，$(3,4)$，$(3,5)$，$(4,5)$，共 $6$ 对。\n\n第一次更新后，山 $4$ 的高度为 $4$，这不会阻挡现有的可见性，但使得山 $4$ 现在可以看到山 $2$，从而使得答案变为 $7$。\n\n第二次更新后，山 $1$ 的高度为 $5$，这不会阻挡现有的可见性，但使得山 $1$ 现在可以看到山 $3$，$4$ 和 $5$，从而使得答案变为 $10$。\n\n第三次更新后，山 $3$ 的高度为 $5$，阻挡了山 $1$ 看到山 $4$，阻挡了山 $2$ 看到山 $4$ 和 $5$，同时由于该山本就可以看到其他所有山，所以并没有使得该山看到更多的山，从而使得答案变为 $7$。\n\n### 测试点性质\n\n - 测试点 $2-5$ 满足 $N,Q \\le 100$。\n - 测试点 $6-11$ 满足 $Q \\le 10$。\n - 测试点 $12-21$ 没有额外性质。"}],"translated_statement":null,"sample_group":[["5\n2 4 3 1 5\n3\n4 3\n1 3\n3 2","7\n10\n7"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}