D. Three Sequencestime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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. OutputPrint 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.ExamplesInput
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
NoteIn 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. 
4
2 -1 7 3
2
2 4 -3
3 4 2

5 5 6 
['constructive algorithms', 'data structures', 'greedy', 'math', '*2200']