1406_D. Three Sequences
You are given a sequence of n integers a_1, a_2, …, a_n.

You have to construct two sequences of integers b and c with length n that satisfy:

  * for every i (1≤ i≤ n) b_i+c_i=a_i 
  * b is non-decreasing, which means that for every 1<i≤ n, b_i≥ b_{i-1} must hold 
  * c is non-increasing, which means that for every 1<i≤ n, c_i≤ 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}, …, 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≤ n≤ 10^5).

The secound line contains n integers a_1,a_2,…,a_n (1≤ i≤ n, -10^9≤ a_i≤ 10^9).

The third line contains an integer q (1≤ q≤ 10^5).

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

Output

Print q+1 lines.

On the i-th (1 ≤ i ≤ 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. 
```python
import sys
import atexit

class Fastio:
    def __init__(self):
        self.ibuf = bytes()
        self.obuf = bytearray()
        self.pil = 0
        self.pir = 0

    def load(self):
        self.ibuf = self.ibuf[self.pil:]
        self.ibuf += sys.stdin.buffer.read(131072)
        self.pil = 0
        self.pir = len(self.ibuf)

    def flush(self):
        sys.stdout.buffer.write(self.obuf)
        self.obuf = bytearray()

    def fastin(self):
        if self.pir - self.pil < 32:
            self.load()
        minus = 0
        x = 0
        while self.ibuf[self.pil] < ord('-'):
            self.pil += 1
        if self.ibuf[self.pil] == ord('-'):
            minus = 1
            self.pil += 1
        while self.ibuf[self.pil] >= ord('0'):
            x = x * 10 + (self.ibuf[self.pil] & 15)
            self.pil += 1
        if minus:
            x = -x
        return x


    def fastout(self, x, end=b'\n'):
        buf = bytearray(end)
        if x == 0:
            buf.append(48)
        else:
            if x < 0:
                self.obuf.append(45)
                x = -x
            while x != 0:
                x, r = x // 10, x % 10
                buf.append(48 + r)
        self.obuf.extend(reversed(buf))
        if len(self.obuf) > 131072:
            self.flush()


fastio = Fastio()
rd = fastio.fastin
wtn = fastio.fastout
atexit.register(fastio.flush)

N = rd()
a = [0] * N
for i in range(N):
    a[i] = rd()
for i in range(N-1, 0, -1):
    a[i] -= a[i-1]
p = 0
for i in range(1, N):
    p += max(0, a[i])
wtn((a[0] + p + 1) // 2)
Q = rd()
for _ in range(Q):
    l, r, x = rd(), rd(), rd()
    l -= 1
    if l != 0:
        p -= max(a[l], 0)
    a[l] += x
    if l != 0:
        p += max(a[l], 0)
    if r != N:
        p -= max(a[r], 0)
        a[r] -= x
        p += max(a[r], 0)
    wtn((a[0] + p + 1) // 2)

```