这是这个问题的困难版本。在这个版本中,我们有疑问。请注意,我们在此版本中没有多个测试用例。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
如果对于所有 $$$i$$$,第 $$$i$$$ 个元素大于或等于 $$$i$$$,则长度为 $$$m$$$ 的数组 $$$b$$$ 是好的。换句话说,$$$b$$$ 是好的当且仅当 $$$b_i \geq i$$$ 对于所有 $$$i$$$ ($$$1 \leq i \leq m$$$)。
给您一个由 $$$n$$$ 正整数组成的数组 $$$a$$$,并询问您 $$$q$$$ 查询。
在每个查询中,都会给出两个整数 $$$p$$$ 和 $$$x$$$ ($$$1 \leq p,x \leq n$$$)。您必须执行 $$$a_p := x$$$ (将 $$$x$$$ 分配给 $$$a_p$$$)。在更新后的数组中,找到索引对 $$$(l, r)$$$ 的数量,其中 $$$1 \le l \le r \le n$$$,这样数组 $$$[a_l, a_{l+1}, \ldots, a_r]$$$ 就是好的。
请注意,所有查询都是独立的,这意味着每次查询后,都会恢复初始数组$$$a$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)。
第三行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — 查询数。
接下来的 $$$q$$$ 行包含两个整数 $$$p_j$$$ 和 $$$x_j$$$ ($$$1 \leq p_j, x_j \leq n$$$) – 第 $$$j$$$ 查询的描述。
输出
对于每个查询,在进行更改后打印合适的索引对的数量。
示例
输入 #1
4 2 4 1 4 3 2 4 3 3 2 1
输出 #1
6 10 5
输入 #2
5 1 1 3 2 1 3 1 3 2 5 4 5
输出 #2
7 9 8
注意
以下是第一个示例的注释。
在第一个查询中,更新 $$$a=[2,4,1,4]$$$ 后。现在 $$$(1,1)$$$、$$$(2,2)$$$、$$$(3,3)$$$、$$$(4,4)$$$、$$$(1,2)$$$ 和 $$$(3,4)$$$ 是合适的对。
在第二个查询中,更新 $$$a=[2,4,3,4]$$$ 后。现在 $$$a$$$ 的所有子数组都很好。
在第三个查询中,更新 $$$a=[2,1,1,4]$$$ 后。现在 $$$(1,1)$$$、$$$(2,2)$$$、$$$(3,3)$$$、$$$(4,4)$$$ 和 $$$(3,4)$$$ 是合适的。