Description

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

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

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

Input Format

第一行一个整数 $n$。

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

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

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

Output Format

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

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

10
10
13

Hint

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