## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Good Subarrays (Hard Version) Codeforces Solution

C2. Good Subarrays (Hard Version)
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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}\ge i$ for all $i$ ($1\le i\le 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\le p,x\le n$). You have to do ${a}_{p}:=x$ (assign $x$ to ${a}_{p}$). In the updated array, find the number of pairs of indices $\left(l,r\right)$, where $1\le l\le r\le n$, such that the array $\left[{a}_{l},{a}_{l+1},\dots ,{a}_{r}\right]$ is good.

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

Input

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},\dots ,{a}_{n}$ ($1\le {a}_{i}\le n$).

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

Each of the next $q$ lines contains two integers ${p}_{j}$ and ${x}_{j}$ ($1\le {p}_{j},{x}_{j}\le n$) – the description of the $j$-th query.

Output

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

Note

Here are notes for first example.

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

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

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