#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const long long mod = 1e9 + 7;
const long long inf = 1e18 + 10;
long long a[N], dif[N], sum[4 * N], mn[4 * N], flg[4 * N], n;
void build(int l = 1, int r = n, int id = 1) {
  if (r - l == 1) {
    sum[id] = mn[id] = abs(dif[l]);
    return;
  }
  int mid = (l + r) / 2;
  build(l, mid, 2 * id);
  build(mid, r, 2 * id + 1);
  sum[id] = sum[2 * id] + sum[2 * id + 1];
  mn[id] = min(mn[2 * id], mn[2 * id + 1]);
  flg[id] =
      flg[2 * id] || flg[2 * id + 1] || (dif[mid - 1] <= 0 && 0 <= dif[mid]);
}
void upd(int p, long long x, int l = 1, int r = n, int id = 1) {
  if (r - l == 1) {
    dif[l] += x;
    sum[id] = mn[id] = abs(dif[l]);
    return;
  }
  int mid = (l + r) / 2;
  if (p < mid)
    upd(p, x, l, mid, 2 * id);
  else
    upd(p, x, mid, r, 2 * id + 1);
  sum[id] = sum[2 * id] + sum[2 * id + 1];
  mn[id] = min(mn[2 * id], mn[2 * id + 1]);
  flg[id] =
      flg[2 * id] || flg[2 * id + 1] || (dif[mid - 1] <= 0 && 0 <= dif[mid]);
}
long long getF(int l, int r, int s = 1, int e = n, int id = 1) {
  if (e <= l || r <= s) return 0;
  if (l <= s && e <= r) return flg[id];
  int mid = (s + e) / 2;
  return getF(l, r, s, mid, 2 * id) || getF(l, r, mid, e, 2 * id + 1) ||
         ((l <= mid - 1 && mid < r) ? (dif[mid - 1] <= 0 && 0 <= dif[mid]) : 0);
}
long long getM(int l, int r, int s = 1, int e = n, int id = 1) {
  if (e <= l || r <= s) return inf;
  if (l <= s && e <= r) return mn[id];
  int mid = (s + e) / 2;
  return min(getM(l, r, s, mid, 2 * id), getM(l, r, mid, e, 2 * id + 1));
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i < n; i++) dif[i] = a[i] - a[i + 1];
  build();
  int q;
  cin >> q;
  while (q--) {
    int t, l, r, x;
    cin >> t >> l >> r >> x;
    if (t == 1) {
      if (getF(l - 1, r + 1))
        cout << sum[1] + 2LL * x << '\n';
      else {
        int L = l - 2, R = r + 1;
        while (1 < R - L) {
          int mid = (L + R) / 2;
          if (0 <= dif[mid])
            L = mid;
          else
            R = mid;
        }
        long long mx = -inf, m1 = getM(l - 1, L), m2 = getM(R + 1, r + 1);
        if (l - 1 <= L && R <= r)
          mx = max(mx, abs(dif[R] + x) - abs(dif[R]) + abs(dif[L] - x) -
                           abs(dif[L]));
        if (m1 != inf) mx = max(mx, x + abs(x - m1) - m1);
        if (m2 != inf) mx = max(mx, x + abs(x - m2) - m2);
        cout << sum[1] + mx << '\n';
      }
    } else {
      upd(l - 1, -x);
      upd(r, x);
    }
  }
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;
const int N = 1e5 + 10;
const long long mod = 1e9 + 7;
const long long inf = 1e18 + 10;
long long a[N], dif[N], sum[4 * N], mn[4 * N], flg[4 * N], n;
void build(int l = 1, int r = n, int id = 1) {
  if (r - l == 1) {
    sum[id] = mn[id] = abs(dif[l]);
    return;
  }
  int mid = (l + r) / 2;
  build(l, mid, 2 * id);
  build(mid, r, 2 * id + 1);
  sum[id] = sum[2 * id] + sum[2 * id + 1];
  mn[id] = min(mn[2 * id], mn[2 * id + 1]);
  flg[id] =
      flg[2 * id] || flg[2 * id + 1] || (dif[mid - 1] <= 0 && 0 <= dif[mid]);
}
void upd(int p, long long x, int l = 1, int r = n, int id = 1) {
  if (r - l == 1) {
    dif[l] += x;
    sum[id] = mn[id] = abs(dif[l]);
    return;
  }
  int mid = (l + r) / 2;
  if (p < mid)
    upd(p, x, l, mid, 2 * id);
  else
    upd(p, x, mid, r, 2 * id + 1);
  sum[id] = sum[2 * id] + sum[2 * id + 1];
  mn[id] = min(mn[2 * id], mn[2 * id + 1]);
  flg[id] =
      flg[2 * id] || flg[2 * id + 1] || (dif[mid - 1] <= 0 && 0 <= dif[mid]);
}
long long getF(int l, int r, int s = 1, int e = n, int id = 1) {
  if (e <= l || r <= s) return 0;
  if (l <= s && e <= r) return flg[id];
  int mid = (s + e) / 2;
  return getF(l, r, s, mid, 2 * id) || getF(l, r, mid, e, 2 * id + 1) ||
         ((l <= mid - 1 && mid < r) ? (dif[mid - 1] <= 0 && 0 <= dif[mid]) : 0);
}
long long getM(int l, int r, int s = 1, int e = n, int id = 1) {
  if (e <= l || r <= s) return inf;
  if (l <= s && e <= r) return mn[id];
  int mid = (s + e) / 2;
  return min(getM(l, r, s, mid, 2 * id), getM(l, r, mid, e, 2 * id + 1));
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i < n; i++) dif[i] = a[i] - a[i + 1];
  build();
  int q;
  cin >> q;
  while (q--) {
    int t, l, r, x;
    cin >> t >> l >> r >> x;
    if (t == 1) {
      if (getF(l - 1, r + 1))
        cout << sum[1] + 2LL * x << '\n';
      else {
        int L = l - 2, R = r + 1;
        while (1 < R - L) {
          int mid = (L + R) / 2;
          if (0 <= dif[mid])
            L = mid;
          else
            R = mid;
        }
        long long mx = -inf, m1 = getM(l - 1, L), m2 = getM(R + 1, r + 1);
        if (l - 1 <= L && R <= r)
          mx = max(mx, abs(dif[R] + x) - abs(dif[R]) + abs(dif[L] - x) -
                           abs(dif[L]));
        if (m1 != inf) mx = max(mx, x + abs(x - m1) - m1);
        if (m2 != inf) mx = max(mx, x + abs(x - m2) - m2);
        cout << sum[1] + mx << '\n';
      }
    } else {
      upd(l - 1, -x);
      upd(r, x);
    }
  }
  return 0;
}

```