题目描述
珂朵莉想让你维护一个长度为 n 的正整数序列 a1,a2,…,an,支持修改序列中某个位置的值。
每次修改后问对序列重复进行以下操作,需要进行几次操作才能使序列变为全 0(询问后序列和询问前相同,不会变为全 0):
选出序列中最大值的出现位置,若有多个最大值则选位置标号最小的一个,设位置为 x,则将 ax−1,ax,ax+1 的值减 1,如果序列中存在小于 0 的数,则把对应的数改为 0。
输入格式
第一行一个整数 n。
接下来 n 行,每行一个整数 ai。
接下来一行一个整数 q。
接下来 q 行,每行两个用空格分隔的整数 xi,yi,表示把 axi 修改为 yi。
输出格式
q 行,每行一个整数表示答案。
样例 #1
样例输入 #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≤n,q≤105,1≤xi≤n,1≤ai,yi≤109。