You are given a sequence of $n$ integers $a_1, a_2, \ldots, a_n$.

You have to construct two sequences of integers $b$ and $c$ with length $n$ that satisfy:  for every $i$ ($1\leq i\leq n$) $b_i+c_i=a_i$  $b$ is non-decreasing, which means that for every $1<i\leq n$, $b_i\geq b_{i-1}$ must hold  $c$ is non-increasing, which means that for every $1<i\leq n$, $c_i\leq c_{i-1}$ must hold 

You have to minimize $\max(b_i,c_i)$. In other words, you have to minimize the maximum number in sequences $b$ and $c$.

Also there will be $q$ changes, the $i$-th change is described by three integers $l,r,x$. You should add $x$ to $a_l,a_{l+1}, \ldots, a_r$. 

You have to find the minimum possible value of $\max(b_i,c_i)$ for the initial sequence and for sequence after each change.


-----Input-----

The first line contains an integer $n$ ($1\leq n\leq 10^5$).

The secound line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\leq i\leq n$, $-10^9\leq a_i\leq 10^9$).

The third line contains an integer $q$ ($1\leq q\leq 10^5$).

Each of the next $q$ lines contains three integers $l,r,x$ ($1\leq l\leq r\leq n,-10^9\leq x\leq 10^9$), desribing the next change. 


-----Output-----

Print $q+1$ lines.

On the $i$-th ($1 \leq i \leq q+1$) line, print the answer to the problem for the sequence after $i-1$ changes.


-----Examples-----
Input
4
2 -1 7 3
2
2 4 -3
3 4 2

Output
5
5
6

Input
6
-9 -10 -9 -6 -5 4
3
2 6 -9
1 2 -10
4 6 -3

Output
3
3
3
1

Input
1
0
2
1 1 -1
1 1 -1

Output
0
0
-1



-----Note-----

In the first test:  The initial sequence $a = (2, -1, 7, 3)$. Two sequences $b=(-3,-3,5,5),c=(5,2,2,-2)$ is a possible choice.  After the first change $a = (2, -4, 4, 0)$. Two sequences $b=(-3,-3,5,5),c=(5,-1,-1,-5)$ is a possible choice.  After the second change $a = (2, -4, 6, 2)$. Two sequences $b=(-4,-4,6,6),c=(6,0,0,-4)$ is a possible choice.

Difficulty: interview

Starter code:

Solutions:
import sys
from sys import stdout
import random
from fractions import Fraction
from math import *
 
def input():
    return sys.stdin.readline().strip()
 
def iinput():
    return int(input())

def finput():
    return float(input())

def tinput():
    return input().split()

def linput():
    return list(input())
 
def rinput():
    return list(map(int, tinput()))

def fiinput():
    return list(map(float, tinput()))
 
def rlinput():
    return list(map(int, input().split()))
def trinput():
    return tuple(rinput())

def srlinput():
    return sorted(list(map(int, input().split())))

def NOYES(fl):
    if fl:
        print("NO")
    else:
        print("YES")
def YESNO(fl):
    if fl:
        print("YES")
    else:
        print("NO")
    
def main():
    def answer(res):
        print((res + 1) // 2)
    n = iinput()
    #k = iinput() 
    #m = iinput() 
    #n = int(sys.stdin.readline().strip()) 
    #n, k = rinput()
    #n, m = rinput()
    #m, k = rinput()
    #n, k, m = rinput()
    #n, m, k = rinput()
    #k, n, m = rinput()
    #k, m, n = rinput() 
    #m, k, n = rinput()
    #m, n, k = rinput()
    #q = srlinput()
    #q = linput()
    q = rlinput()
    w = [0] + [q[i] - q[i - 1] for i in range(1, n)]
    res = q[0] + sum([max(w[i], 0) for i in range(1, n)])
    answer(res)
    k = iinput()
    for o in range(k):
        l, r, x = rinput()
        if l == 1:
            res += x        
        else:
            res = res - max(0, w[l - 1]) + max(0, w[l - 1] + x); w[l - 1] += x 
        if r != n:
            res = res - max(0, w[r]) + max(0, w[r] - x); w[r] -= x 
        answer(res)
    
        
    
    
        
    

for i in range(1):
    main()


from collections import deque
import sys

def max(a,b):
    if a>b:
        return a
    else:
        return b

def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    A = list(map(int,input().split()))
    B = [A[i+1]-A[i] for i in range(N-1)]
    S = 0
    for i in range(N-1):
        if A[i+1]>A[i]:
            S += A[i+1] - A[i]
    if (A[0]+S)%2==0:
        print((A[0]+S)//2)
    else:
        print((A[0]+S+1)//2)

    Q = int(input())
    for i in range(Q):    
        L,R,X = list(map(int,input().split()))

        L,R = L-1,R-1

        if L>0:
            temp = B[L-1]
            B[L-1] += X
            S = S - max(0,temp) + max(0,B[L-1])
        else:
            A[0] += X
        if R<N-1:
            temp = B[R]
            B[R] -= X
            S = S - max(0,temp) + max(0,B[R])

        if (A[0]+S)%2==0:
            print((A[0]+S)//2)
        else:
            print((A[0]+S+1)//2)
            
def __starting_point():
    main()



__starting_point()

import sys
# sys.stdin = open("input.txt")

def calc(a0, db, dc):
    b0 = (a0 - db) // 2
    c0 = a0 - b0
    c1 = (a0 - dc) // 2
    b1 = a0 - c1
    return min(max(b0 + db, c0), max(b1 + db, c1))

def main():
    n = int(input())
    A = [int(a) for a in input().split()]
    D = [A[i+1] - A[i] for i in range(n - 1)]
    a0 = A[0]
    db = sum([d for d in D if d > 0])
    dc = sum([d for d in D if d < 0])

    q = int(input())
    ans = [calc(a0, db, dc)]
    for i in range(q):
        l, r, x = list(map(int, input().split()))
        if l > 1:
            if D[l-2] < 0:
                dc -= D[l-2]
            else:
                db -= D[l-2]
            D[l-2] += x
            if D[l-2] < 0:
                dc += D[l-2]
            else:
                db += D[l-2]
        if r < n:
            if D[r-1] < 0:
                dc -= D[r-1]
            else:
                db -= D[r-1]
            D[r-1] -= x
            if D[r-1] < 0:
                dc += D[r-1]
            else:
                db += D[r-1]
        if l == 1:
            a0 += x
        ans.append(calc(a0, db, dc))
    print("\n".join(map(str, ans)))


def __starting_point():
    main()

__starting_point()

import sys
input = sys.stdin.readline

n = int(input())

a = list(map(int, input().split()))
start = a[0]

diffs =[]
for i in range(n-1):
	diffs.append(a[i+1]-a[i])
pos = 0
for v in diffs:
	if v>0:
		pos+=v

final= []

def out(ans):
	final.append((ans+1)//2)
		
out(pos+start)

q = int(input())
for _ in range(q):
	l, r, x = map(int, input().split())
	if l>1:
		if diffs[l-2] >= 0:
			pos -= diffs[l-2]
		diffs[l-2] += x
		if diffs[l-2] >= 0:
			pos += diffs[l-2]	
	else:
		start += x
		
	if r<n:
		if diffs[r-1] >= 0:
			pos -= diffs[r-1]
		diffs[r-1] -= x
		if diffs[r-1] >= 0:
			pos += diffs[r-1]
		
	out(pos+start)
print('\n'.join(map(str,final)))

import sys

n = int(sys.stdin.readline().strip())
a = list(map(int, sys.stdin.readline().strip().split()))
d = []
b = 0
c = 0
F = a[0]
L = a[-1]
for i in range (1, n):
    x = a[i] - a[i-1]
    if x >= 0:
        b = b + x
    else:
        c = c - x
    d.append(x)
Q = int(sys.stdin.readline().strip())
for q in range (0, Q + 1):
    if q > 0:
        l, r, x = list(map(int, sys.stdin.readline().strip().split()))
    else:
        l, r, x = 1, 1, 0
    if x != 0 and l > 1:    
        if x >= 0 and d[l-2] >= 0:
            b = b + x
        elif x >= 0 and d[l-2] < 0:
            b = b + x - min(-d[l-2], x)
            c = c - min(-d[l-2], x)
        elif x < 0 and d[l-2] >= 0:
            c = c - min(d[l-2], -x) - x
            b = b - min(d[l-2], -x)
        elif x < 0 and d[l-2] < 0:
            c = c - x
        d[l-2] = d[l-2] + x
    elif x != 0 and l == 1:
        F = F + x
    if x != 0 and r < n:
        if x <= 0 and d[r-1] >= 0:
            b = b - x
        elif x <= 0 and d[r-1] < 0:
            b = b - x - min(-x, -d[r-1])
            c = c - min(-x, -d[r-1])
        elif x > 0 and d[r-1] >= 0:
            c = c - min(x, d[r-1]) + x
            b = b - min(x, d[r-1])
        elif x > 0 and d[r-1] < 0:
            c = c + x
        d[r-1] = d[r-1] - x
    elif x != 0 and r == n:
        L = L + x
    print((L + F + b + c + 3) // 4)

import sys

input = sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))

diff = [0 for i in range(n)]

for i in range(1,n):
    diff[i] = a[i] - a[i-1]

S = 0
for i in range(1,n):
    if diff[i]>=0:
        S += diff[i]
first = a[0]
ans = []

res = S + first
ans.append((res+1)//2)

Q = int(input())
for _ in range(Q):
    l,r,x = map(int,input().split())
    l=l-1
    r=r-1
    #diff[l] += x
    #diff[r+1] -=x
    if l==0:
        first += x
    else:
        if diff[l]>=0:
            S -= diff[l]
        diff[l] += x
        if diff[l]>=0:
            S += diff[l]
    if r+1<n:
        if diff[r+1]>=0:
            S -= diff[r+1]
        diff[r+1] -= x
        if diff[r+1]>=0:
            S += diff[r+1]
    res = S + first
    ans.append((res+1)//2)

for a in ans:
    print(a)

n = int(input())
aaa = list(map(int, input().split()))
diff = []
score = 0
prv = 0
for a in aaa:
    d = a - prv
    diff.append(d)
    if d > 0:
        score += d
    prv = a
buf = [(score + min(0, diff[0]) + 1) // 2]

q = int(input())
for _ in range(q):
    l, r, x = list(map(int, input().split()))
    l -= 1
    dl1 = diff[l]
    diff[l] += x
    dl2 = diff[l]
    score += max(0, dl2) - max(0, dl1)

    if r < n:
        dr1 = diff[r]
        diff[r] -= x
        dr2 = diff[r]
        score += max(0, dr2) - max(0, dr1)

    buf.append((score + min(0, diff[0]) + 1) // 2)

print('\n'.join(map(str, buf)))


import math
import sys
  
input = sys.stdin.readline

n = int(input())
li = list(map(int, input().split()))


minuses = 0
diff = []
for i in range(1, len(li)):
    diff.append(li[i] - li[i-1])
    if li[i] < li[i-1]:
        minuses += (li[i-1]-li[i])

ll = li[-1]
print(math.ceil((minuses+ll)/2))

for i in range(int(input())):
    l, r, x = list(map(int, input().split()))
    if l > 1:
        old = diff[l-2]
        diff[l-2] += x
        minuses += max(-(old+x), 0) - max(-old, 0)
    
    if r < n:
        old = diff[r-1]
        diff[r-1] -= x
        minuses += max(-(old-x), 0) - max(-old, 0)

    if r == n:
        ll += x
        
    print(math.ceil((minuses+ll)/2))


import sys
input = sys.stdin.readline

n=int(input())
A=list(map(int,input().split()))

PLUS=[0]*(n-1)

for i in range(n-1):
    PLUS[i]=A[i+1]-A[i]

S=0
for p in PLUS:
    if p>0:
        S+=p

print((S+A[0]+1)//2)

Q=int(input())
for queries in range(Q):
    l,r,x=list(map(int,input().split()))

    if l>=2:
        ptemp=PLUS[l-2]
        PLUS[l-2]+=x

        if x>0:
            if PLUS[l-2]>0:
                S+=PLUS[l-2]-max(0,ptemp)
        else:
            if ptemp>0:
                S-=ptemp-max(0,PLUS[l-2])
    else:
        A[0]+=x

    if r<n:
        ptemp=PLUS[r-1]
        PLUS[r-1]-=x

        if x<0:
            if PLUS[r-1]>0:
                S+=PLUS[r-1]-max(0,ptemp)
        else:
            if ptemp>0:
                S-=ptemp-max(0,PLUS[r-1])

    print((S+A[0]+1)//2)

        
            
            
    


#Python Template

from sys import stdin, stdout
from math import ceil

def main():
	t = 1
	for _ in range(t):
		n = int(stdin.readline())
		a = [int(i) for i in stdin.readline().split()]
		q = int(stdin.readline())
		diffs = [0]*(n-1)
		start = a[0]
		for i in range(n-1):
			diffs[i] = a[i+1] - a[i]

		upstep = 0
		for d in diffs:
			if d > 0:
				upstep += d
		val = ceil((start + upstep)/2.0)
		#print(diffs)
		print(val)
		#print()

		for _ in range(q):
			l, r, x = [int(i) for i in stdin.readline().split()]
			l-=1
			r-=1
			if l == 0:
				start += x
			else:
				old = diffs[l-1]
				diffs[l-1] += x
				new = diffs[l-1]
				if old > 0:
					upstep -= old
				if new > 0:
					upstep += new
			if r != n-1:
				old = diffs[r]
				diffs[r] -= x
				new = diffs[r]
				if old > 0:
					upstep -= old
				if new > 0:
					upstep += new
			#print("Steps: {0}".format(upstep))
			#print(diffs)
			#print("Start: {0}".format(start))

			val = ceil((start + upstep)/2.0) 
			#print("Answer: {0}".format(val))
			print(val)



main()