B'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: 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. The first line contains an integer n ( 1 <= q n <= q 10^5 ). The secound line contains n integers a_1,a_2, ldots,a_n ( 1 <= q i <= q n , -10^9 <= q a_i <= q 10^9 ). The third line contains an integer q ( 1 <= q q <= q 10^5 ). Each of the next q lines contains three integers l,r,x ( 1 <= q l <= q r <= q n,-10^9 <= q x <= q 10^9 ), desribing the next change. Print q+1 lines. On the i -th ( 1 <= q i <= q q+1 ) line, print the answer to the problem for the sequence after i-1 changes. In the first test: '...