CF1736C2.Good Subarrays (Hard Version)

This is the hard version of this problem. In this version, we have queries. Note that we do not have multiple test cases in this version. You can make hacks only if both versions of the problem are solved.

An array $b$ of length $m$ is good if for all $i$ the $i$-th element is greater than or equal to $i$. In other words, $b$ is good if and only if $b_i \geq i$ for all $i$ ($1 \leq i \leq m$).

You are given an array $a$ consisting of $n$ positive integers, and you are asked $q$ queries.

In each query, you are given two integers $p$ and $x$ ($1 \leq p,x \leq n$). You have to do $a_p := x$ (assign $x$ to $a_p$). In the updated array, find the number of pairs of indices $(l, r)$, where $1 \le l \le r \le n$, such that the array $[a_l, a_{l+1}, \ldots, a_r]$ is good.

Note that all queries are independent, which means after each query, the initial array $a$ is restored.

这是本题的困难版本。在该版本中，我们需要处理多个查询。注意，本版本中不包含多组测试数据。只有当本题的两个版本（简单版与困难版）均被解决时，才允许进行 Hack。

长度为 $m$ 的数组 $b$ 被称为好数组，当且仅当对所有 $i$，第 $i$ 个元素不小于 $i$。换言之，$b$ 是好数组当且仅当对所有 $i$（$1 \leq i \leq m$）满足 $b_i \geq i$。

给定一个由 $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$ 都会恢复为初始状态。

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).

The third line contains an integer $q$ ($1 \leq q \leq 2 \cdot 10^5$) — the number of queries.

Each of the next $q$ lines contains two integers $p_j$ and $x_j$ ($1 \leq p_j, x_j \leq n$) – the description of the $j$-th query.

第一行包含一个整数 $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$ 个查询的描述。

For each query, print the number of suitable pairs of indices after making the change.

对于每个查询，请输出执行更改后满足条件的索引对的数量。

Here are notes for first example.

In first query, after update $a=[2,4,1,4]$. Now $(1,1)$, $(2,2)$, $(3,3)$, $(4,4)$, $(1,2)$, and $(3,4)$ are suitable pairs.

In second query, after update $a=[2,4,3,4]$. Now all subarrays of $a$ are good.

In third query, after update $a=[2,1,1,4]$. Now $(1,1)$, $(2,2)$, $(3,3)$, $(4,4)$, and $(3,4)$ are suitable.

以下是第一个示例的说明。

在第一次查询中，更新后 $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)$。