Это сложная версия этой задачи. В этой версии присутствуют запросы. Обратите внимание, что в этой версии в каждом тесте ровно один набор входных данных. Вы можете делать взломы только если обе версии задачи решены.
Массив \(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\) восстанавливается к изначальному состоянию.
Выходные данные
Для каждого запроса выведите количество подходящих пар индексов после изменения массива.
Примечание
Ниже находятся примечания к первому примеру.
В первом запросе \(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)\) являются подходящими парами.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 4 1 4
3
2 4
3 3
2 1
|
6
10
5
|
|
2
|
5
1 1 3 2 1
3
1 3
2 5
4 5
|
7
9
8
|