#include <bits/stdc++.h>
using namespace std;
template <typename c>
void amax(c &x, c y) {
  x = max(x, y);
}
template <typename c>
void amin(c &x, c y) {
  x = min(x, y);
}
const long long inf = 1e14;
const long long maxn = 1e5 + 11;
long long a[maxn], seg[maxn << 2], n, q, t, l, r, x, f, ans;
set<long long> sx, sxx;
long long query(long long node, long long l, long long r, long long ql,
                long long qr) {
  if (ql >= r || qr <= l) return inf;
  if (l >= ql && r <= qr) {
    return seg[node];
  }
  long long mid = l + r >> 1;
  return min(query(node << 1, l, mid, ql, qr),
             query(node << 1 | 1, mid, r, ql, qr));
}
void update(long long node, long long l, long long r, long long ind,
            long long val) {
  if (ind < l || ind >= r) return;
  if (r == l + 1) {
    seg[node] = val;
    return;
  }
  long long mid = l + r >> 1;
  update(node << 1, l, mid, ind, val);
  update(node << 1 | 1, mid, r, ind, val);
  seg[node] = min(seg[node << 1], seg[node << 1 | 1]);
}
long long test(long long i) {
  long long ret = f;
  if (i >= 1) ret += abs(a[i] + x) - abs(a[i]);
  if (i + 1 < n) ret += abs(a[i + 1] - x) - abs(a[i + 1]);
  return ret;
}
void repair(long long i) {
  if (i < 1 || i >= n - 1)
    ;
  update(1, 1, n - 1, i, max(-a[i], 0LL) + max(a[i + 1], 0LL));
}
int32_t main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for (long long i = 0; i < n; i++) cin >> a[i];
  for (long long i = n - 1; i >= 1; i--) {
    a[i] -= a[i - 1];
    f += abs(a[i]);
  }
  for (long long i = 1; i < n - 1; i++) repair(i);
  cin >> q;
  while (q--) {
    cin >> t >> l >> r >> x;
    l--;
    if (t == 1) {
      if (r == l + 1)
        cout << test(l) << endl;
      else {
        ans = test(l);
        amax(ans, test(r - 1));
        l++, r--;
        if (r > l) {
          long long temp = query(1, 1, n - 1, l, r);
          temp = min(temp, x);
          amax(ans, f + 2 * (x - temp));
        }
        cout << ans << endl;
      }
    } else {
      if (l >= 1) {
        f -= abs(a[l]);
        a[l] += x;
        f += abs(a[l]);
      }
      if (r < n) {
        f -= abs(a[r]);
        a[r] -= x;
        f += abs(a[r]);
      }
      repair(l - 1);
      repair(l);
      repair(r - 1);
      repair(r);
    }
  }
  return 0;
}

### Prompt

Your task is to create a cpp solution to the following problem:

Fafa has an array A of n positive integers, the function f(A) is defined as <image>. He wants to do q queries of two types:

  * 1 l r x — find the maximum possible value of f(A), if x is to be added to one element in the range [l, r]. You can choose to which element to add x. 
  * 2 l r x — increase all the elements in the range [l, r] by value x. 



Note that queries of type 1 don't affect the array elements.

Input

The first line contains one integer n (3 ≤ n ≤ 105) — the length of the array.

The second line contains n positive integers a1, a2, ..., an (0 < ai ≤ 109) — the array elements.

The third line contains an integer q (1 ≤ q ≤ 105) — the number of queries. 

Then q lines follow, line i describes the i-th query and contains four integers ti li ri xi <image>. 

It is guaranteed that at least one of the queries is of type 1.

Output

For each query of type 1, print the answer to the query.

Examples

Input

5
1 1 1 1 1
5
1 2 4 1
2 2 3 1
2 4 4 2
2 3 4 1
1 3 3 2


Output

2
8


Input

5
1 2 3 4 5
4
1 2 4 2
2 2 4 1
2 3 4 1
1 2 4 2


Output

6
10

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename c>
void amax(c &x, c y) {
  x = max(x, y);
}
template <typename c>
void amin(c &x, c y) {
  x = min(x, y);
}
const long long inf = 1e14;
const long long maxn = 1e5 + 11;
long long a[maxn], seg[maxn << 2], n, q, t, l, r, x, f, ans;
set<long long> sx, sxx;
long long query(long long node, long long l, long long r, long long ql,
                long long qr) {
  if (ql >= r || qr <= l) return inf;
  if (l >= ql && r <= qr) {
    return seg[node];
  }
  long long mid = l + r >> 1;
  return min(query(node << 1, l, mid, ql, qr),
             query(node << 1 | 1, mid, r, ql, qr));
}
void update(long long node, long long l, long long r, long long ind,
            long long val) {
  if (ind < l || ind >= r) return;
  if (r == l + 1) {
    seg[node] = val;
    return;
  }
  long long mid = l + r >> 1;
  update(node << 1, l, mid, ind, val);
  update(node << 1 | 1, mid, r, ind, val);
  seg[node] = min(seg[node << 1], seg[node << 1 | 1]);
}
long long test(long long i) {
  long long ret = f;
  if (i >= 1) ret += abs(a[i] + x) - abs(a[i]);
  if (i + 1 < n) ret += abs(a[i + 1] - x) - abs(a[i + 1]);
  return ret;
}
void repair(long long i) {
  if (i < 1 || i >= n - 1)
    ;
  update(1, 1, n - 1, i, max(-a[i], 0LL) + max(a[i + 1], 0LL));
}
int32_t main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for (long long i = 0; i < n; i++) cin >> a[i];
  for (long long i = n - 1; i >= 1; i--) {
    a[i] -= a[i - 1];
    f += abs(a[i]);
  }
  for (long long i = 1; i < n - 1; i++) repair(i);
  cin >> q;
  while (q--) {
    cin >> t >> l >> r >> x;
    l--;
    if (t == 1) {
      if (r == l + 1)
        cout << test(l) << endl;
      else {
        ans = test(l);
        amax(ans, test(r - 1));
        l++, r--;
        if (r > l) {
          long long temp = query(1, 1, n - 1, l, r);
          temp = min(temp, x);
          amax(ans, f + 2 * (x - temp));
        }
        cout << ans << endl;
      }
    } else {
      if (l >= 1) {
        f -= abs(a[l]);
        a[l] += x;
        f += abs(a[l]);
      }
      if (r < n) {
        f -= abs(a[r]);
        a[r] -= x;
        f += abs(a[r]);
      }
      repair(l - 1);
      repair(l);
      repair(r - 1);
      repair(r);
    }
  }
  return 0;
}

```