C2. Хорошие подмассивы (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия этой задачи. В этой версии присутствуют запросы. Обратите внимание, что в этой версии в каждом тесте ровно один набор входных данных. Вы можете делать взломы только если обе версии задачи решены.

Массив $$$b$$$ длины $$$m$$$ является хорошим, если $$$i$$$-й элемент больше либо равен $$$i$$$ для всех $$$i$$$. Другими словами, $$$b$$$ хороший, если и только если $$$b_i \geq i$$$ для всех $$$i$$$ ($$$1 \leq i \leq m$$$).

Вам дан массив $$$a$$$, состоящий из $$$n$$$ положительных целых чисел, а также $$$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$$$-го запроса.

Выходные данные

Для каждого запроса выведите количество подходящих пар индексов после изменения массива.

Примеры
Входные данные
4
2 4 1 4
3
2 4
3 3
2 1
Выходные данные
6
10
5
Входные данные
5
1 1 3 2 1
3
1 3
2 5
4 5
Выходные данные
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)$$$ являются подходящими парами.