Description

Chtholly wants you to maintain a positive integer sequence of length $n$, $a_1,a_2,\ldots,a_n$, supporting updates that modify the value at some position.

After each update, you are asked: if we repeatedly perform the following operation on the sequence, how many operations are needed to make the sequence become all $0$ (after the query, the sequence is the same as before the query; it will not actually become all $0$)?

Choose a position where the maximum value in the sequence occurs. If there are multiple maximum values, choose the one with the smallest index. Let the position be $x$. Then decrease $a_{x-1},a_x,a_{x+1}$ by $1$. If there exists a number less than $0$ in the sequence, change that number to $0$.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain one integer $a_i$.

The next line contains an integer $q$.

The next $q$ lines each contain two integers $x_i,y_i$ separated by a space, meaning to modify $a_{x_i}$ to $y_i$.

Output Format

Output $q$ lines, each containing one integer representing the answer.

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

10
10
13

Hint

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078

Constraints: $1\leq n,q\leq 10^5$, $1\leq x_i\leq n$, $1\leq a_i,y_i\leq 10^9$.

Translated by ChatGPT 5