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. 
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
  scanf("%d", &n);
  vector<long long> a(n + 2);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  vector<long long> f(n + 2);
  f[1] = a[1];
  for (int i = 2; i <= n; i++) {
    f[i] = a[i] - a[i - 1];
  }
  long long sum = a[1];
  for (int i = 2; i <= n; i++) {
    if (f[i] > 0) sum += f[i];
  }
  long long ans;
  if (sum >= 0) {
    ans = sum / 2 + sum % 2;
  } else {
    ans = sum / 2;
  }
  printf("%lld\n", ans);
  int q;
  scanf("%d", &q);
  while (q--) {
    int l, r;
    long long x;
    scanf("%d%d%lld", &l, &r, &x);
    long long tl = f[l];
    long long tr = f[r + 1];
    if (x != 0) {
      f[l] += x;
      f[r + 1] -= x;
      if (x > 0) {
        if (l == 1) sum += x;
        if (tl <= 0 && f[l] > 0 && l != 1)
          sum += f[l];
        else if (tl > 0 && l != 1)
          sum += x;
        if (r + 1 <= n) {
          if (tr > 0) sum -= min(x, tr);
        }
      } else {
        if (l == 1) sum += x;
        if (tl > 0 && l != 1) sum -= min(tl, -x);
        if (r + 1 <= n) {
          if (tr <= 0 && f[r + 1] > 0)
            sum += f[r + 1];
          else if (tr > 0)
            sum -= x;
        }
      }
    }
    if (sum >= 0) {
      ans = sum / 2 + sum % 2;
    } else {
      ans = sum / 2;
    }
    printf("%lld\n", ans);
  }
  return 0;
}
