上课的时候，小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行，每行一个整数表示结果。