Background

【You seem very happy.】
Because I rarely get a chance to go out alone with you.
Or rather, it seems like we never really had before, right?
【Didn’t we go to lots of places together when we first met?】

Huh? Ah... right.
But, well... it just feels kind of different from now.
Alright, hurry up, let’s go!
【Chtholly...】


Seriously, don’t make a sound like you’re about to cry. You’re an adult, aren’t you?
I’m fine, look.
Eh...
Ah, th-this kid is also fine.

【If anything unexpected happens, I...】
【I thought I would lose you again, this close...】


A red-haired girl.
Is
Watching here.

Problem 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