问题 C: C

问题 C: C

时间限制: 1 Sec  内存限制: 128 MB
提交: 27  解决: 1
[状态] [讨论版] [提交] [命题人:]
题目描述

上课的时候,小z得到了一张纸条,上面写了一个整数的序列A,和一些文字。这个序列中有N个整数,可以对序列A中任意位置的数字进行修改,每次只能修改一个位置上的数字,并且修改完后会产生一次询问。询问的内容如下:将当前的序列A的每一个元素拷贝到序列C中,然后对C序列进行操作。从序列C中选出一个最大值,如果有多个选择下标最小的一个,然后将该最大值及其相邻的两个值减去1,最小为0,但是0依然可以做减一操作,如果一次操作中发现序列中有负数,则将该数字调整为0,问题是,最少需要多少次操作才可以将C序列的元素全部置为0。小z心想,这么简单的问题,浪费时间,于是趴下睡觉了。作为小z的同桌,出于好奇,你接过了纸条,开始研究起来。

输入

第一行一个整数N,表示序列A的长度(1 <= N <= 100000)

接下来一行N个元素,表示序列A(1 <= A[i] <= 100000000)

接下来一行一个数字M,表示M次操作(1 <= M <= 100000)

接下来M行,每行两个数字,x和y,表示将A[x]的值置为y,即A[x] = y(1 <= y <= 100000000, 1 <= x <= N)

输出

M行,每行一个整数表示结果。

样例输入 Copy
3
1 2 3
1
1 3
样例输出 Copy
6