# D. Three Sequences SOLUTION CODEFORCES

## Three Sequences SOLUTION

You are given a succession of n numbers a1,a2,… ,an. You need to develop two arrangements of whole numbers b and c with length n that fulfill:

for each I (1≤i≤n) bi+ci=ai

b is non-diminishing, which implies that for each 1<i≤n, bi≥bi−1 must hold

c is non-expanding, which implies that for each 1<i≤n, ci≤ci−1 must hold

You need to limit max(bi,ci). At the end of the day, you need to limit the most extreme number in successions b and c.

Additionally there will be q changes, the I-th change is portrayed by three numbers l,r,x. You should add x to al,al+1,… ,ar.

You need to locate the base conceivable estimation of max(bi,ci) for the underlying arrangement and for succession after each change.

Information

The main line contains a whole number n (1≤n≤105).

The secound line contains n numbers a1,a2,… ,a (1≤i≤n, −109≤ai≤109).

The third line contains a number q (1≤q≤105).

Every one of the following q lines contains three numbers l,r,x (1≤l≤r≤n,−109≤x≤109), desribing the following change.

Yield

Print q+1 lines.

On the I-th (1≤i≤q+1) line, print the response to the issue for the succession after i−1 changes.

Models

inputCopy

2 – 1 7 3

2 4 – 3

3 4 2

outputCopy

inputCopy

– 9 – 10 – 9 – 6 – 5 4

2 6 – 9

1 2 – 10

4 6 – 3

outputCopy

inputCopy

1 – 1

1 – 1

outputCopy

– 1

Note

In the main test:

The underlying grouping a=(2,−1,7,3). Two successions b=(−3,−3,5,5),c=(5,2,2,−2) is a potential decision.

After the primary change a=(2,−4,4,0). Two successions b=(−3,−3,5,5),c=(5,−1,−1,−5) is a potential decision.

After the second change a=(2,−4,6,2). Two arrangements b=(−4,−4,6,6),c=(6,0,0,−4) is a potential decision.