[Ynoi2015]纵使日薄西山

题目背景

【你好像很开心嘛】 因为很少有机会和你单独出来走动嘛 应该说,好像以前一直没有吧? 【我们第一次见面的时候,不就一起逛过很多地方吗?】 ![](https://cdn.luogu.com.cn/upload/pic/45549.png) 诶?啊...对 但是那个...总觉得和现在的感觉不太一样嘛 好吧,快点走吧! 【珂朵莉...】 ![](https://cdn.luogu.com.cn/upload/pic/45550.png) ![](https://cdn.luogu.com.cn/upload/pic/45551.png) 真是的,别发出那种像是快哭的声音啦,你是大人吧 我没事,你看 诶... 啊,这...这孩子也没事 ![](https://cdn.luogu.com.cn/upload/pic/45552.png) 【要是出现什么意外,我...】 【我还以为自己又会在这么近的地方失去你...】 ![](https://cdn.luogu.com.cn/upload/pic/45553.png) ![](https://cdn.luogu.com.cn/upload/pic/45554.png) 红色头发的少女 在 看着这里

题目描述

珂朵莉想让你维护一个长度为 $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$ 行,每行一个整数表示答案。

输入输出样例

输入样例 #1

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

输出样例 #1

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$。