题目背景

【你好像很开心嘛】
因为很少有机会和你单独出来走动嘛
应该说，好像以前一直没有吧？
【我们第一次见面的时候，不就一起逛过很多地方吗？】
诶？啊...对
但是那个...总觉得和现在的感觉不太一样嘛
好吧，快点走吧！
【珂朵莉...】


真是的，别发出那种像是快哭的声音啦，你是大人吧
我没事，你看
诶...
啊，这...这孩子也没事

【要是出现什么意外，我...】
【我还以为自己又会在这么近的地方失去你...】


红色头发的少女
在
看着这里

题目描述

珂朵莉想让你维护一个长度为 $n$ 的正整数序列 $a_1,a_2,\ldots,a_n$，支持修改序列中某个位置的值。

每次修改后问对序列重复进行以下操作，需要进行几次操作才能使序列变为全 $0$（询问后序列和询问前相同，不会变为全 $0$）：

选出序列中最大值的出现位置，若有多个最大值则选位置标号最小的一个，设位置为 $x$，则将 $a_{x-1},a_x,a_{x+1}$ 的值减 $1$，如果序列中存在小于 $0$ 的数，则把对应的数改为 $0$。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行一个整数 $a_i$。

接下来一行一个整数 $q$。

接下来 $q$ 行，每行两个用空格分隔的整数 $x_i,y_i$，表示把 $a_{x_i}$ 修改为 $y_i$。

输出格式

$q$ 行，每行一个整数表示答案。

4
3
6
6
4
3
4 4
3 5
1 8

10
10
13

提示

Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

$1\leq n,q\leq 10^5$，$1\leq x_i\leq n$，$1\leq a_i,y_i\leq 10^9$。