[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≤𝑖≤𝑚$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≤𝑝,𝑥≤𝑛$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 (𝑙,𝑟)$(l,r)$, where 1≤𝑙≤𝑟≤𝑛$1\le l\le r\le n$, such that the array [𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟]$[a_l,a_{l+1},\dots ,a_r]$ 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≤𝑛≤2⋅105$1\le n\le 2\cdot {10}^5$).

The second line contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤𝑛$1\le a_i\le n$).

The third line contains an integer 𝑞$q$ (1≤𝑞≤2⋅105$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≤𝑝𝑗,𝑥𝑗≤𝑛$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 𝑎=[2,4,1,4]$a=[2,4,1,4]$. Now (1,1)$(1,1)$, (2,2)$(2,2)$, (3,3)$(3,3)$, (4,4)$(4,4)$, (1,2)$(1,2)$, and (3,4)$(3,4)$ are suitable pairs.

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

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