#include <bits/stdc++.h>
using namespace std;
int n, q;
int a[100010];
pair<long long, int> tmin[2][4 * 100010];
long long ta[100010];
long long t[100010];
const long long inf = (long long)1e18 + 12345;
void update(int pos, long long val) {
  for (; pos < n; pos |= (pos + 1)) {
    t[pos] += val;
  }
}
long long getsum(int r) {
  long long result = 0;
  for (; r >= 0; r = (r & (r + 1)) - 1) {
    result += t[r];
  }
  return result;
}
long long getnum(int r) { return getsum(r); }
void update_ta(int pos, long long val) {
  for (; pos < n; pos |= (pos + 1)) {
    ta[pos] += val;
  }
}
long long get_ta(int r) {
  long long result = 0;
  for (; r >= 0; r = (r & (r + 1)) - 1) result += ta[r];
  return result;
}
long long get_ta(int l, int r) { return get_ta(r) - get_ta(l - 1); }
pair<long long, int> combine(pair<long long, int> lhs,
                             pair<long long, int> rhs) {
  if (lhs.first < rhs.first) return lhs;
  return rhs;
}
pair<long long, int> getmin(int t, int v, int vl, int vr, int l, int r) {
  if (l > vr || r < vl) return {inf, -1};
  if (l <= vl && vr <= r) return tmin[t][v];
  int vm = (vl + vr) >> 1;
  return combine(getmin(t, 2 * v, vl, vm, l, r),
                 getmin(t, 2 * v + 1, vm + 1, vr, l, r));
}
void update(int t, int v, int vl, int vr, int pos, long long val) {
  if (vl == vr) {
    tmin[t][v] = {val, pos};
    return;
  }
  int vm = (vl + vr) >> 1;
  if (pos <= vm)
    update(t, 2 * v, vl, vm, pos, val);
  else
    update(t, 2 * v + 1, vm + 1, vr, pos, val);
  tmin[t][v] = combine(tmin[t][2 * v], tmin[t][2 * v + 1]);
}
void build(int v, int vl, int vr) {
  if (vl == vr) {
    update(vl, a[vl]);
    update(vl + 1, -a[vl]);
    if (vl + 1 < n) {
      update_ta(vl, abs(a[vl] - a[vl + 1]));
    }
    if (vl > 0 && vr + 1 < n) {
      long long d1 = a[vl] - a[vl - 1];
      long long d2 = a[vr] - a[vr + 1];
      long long lg = min(abs(min(0ll, d1)), abs(min(0ll, d2)));
      long long rg = abs(min(0ll, d1)) + abs(min(0ll, d2));
      update(0, 1, 0, n - 1, vl, lg);
      update(1, 1, 0, n - 1, vl, rg);
    } else {
      update(0, 1, 0, n - 1, vl, inf);
      update(1, 1, 0, n - 1, vl, inf);
    }
    return;
  }
  int vm = (vl + vr) >> 1;
  build(2 * v, vl, vm);
  build(2 * v + 1, vm + 1, vr);
}
long long solve(int pos, int val) {
  long long oldnum = getnum(pos);
  long long left, right;
  if (pos > 0) {
    left = getnum(pos - 1);
    update_ta(pos - 1, abs(oldnum + val - left) - get_ta(pos - 1, pos - 1));
  }
  if (pos + 1 < n) {
    right = getnum(pos + 1);
    update_ta(pos, abs(oldnum + val - right) - get_ta(pos, pos));
  }
  long long result = get_ta(n - 1);
  if (pos > 0) {
    update_ta(pos - 1, abs(oldnum - left) - get_ta(pos - 1, pos - 1));
  }
  if (pos + 1 < n) {
    update_ta(pos, abs(oldnum - right) - get_ta(pos, pos));
  }
  return result;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  build(1, 0, n - 1);
  cin >> q;
  for (int i = 0; i < q; i++) {
    int t, l, r, x;
    cin >> t >> l >> r >> x;
    l--, r--;
    if (t == 1) {
      long long an = 0;
      if (l == 0) {
        an = max(an, solve(l, x));
        l++;
      }
      if (r + 1 == n) {
        an = max(an, solve(r, x));
        r--;
      }
      if (l <= r) {
        pair<long long, int> p = getmin(1, 1, 0, n - 1, l, r);
        if (p.first > x) p = getmin(0, 1, 0, n - 1, l, r);
        if (p.first > x) p.second = l;
        an = max(an, solve(p.second, x));
      }
      cout << an << '\n';
    } else {
      long long old_l = getnum(l);
      long long old_r = getnum(r);
      update(l, x);
      update(r + 1, -x);
      long long num_l = getnum(l);
      long long num_r = getnum(r);
      long long num_l_1, num_r_1;
      if (l > 0) {
        num_l_1 = getnum(l - 1);
        update_ta(l - 1, abs(num_l - num_l_1) - get_ta(l - 1, l - 1));
      }
      if (r + 1 < n) {
        num_r_1 = getnum(r + 1);
        update_ta(r, abs(num_r - num_r_1) - get_ta(r, r));
      }
      vector<int> vals;
      vals.push_back(l - 1);
      vals.push_back(l);
      vals.push_back(r);
      vals.push_back(r + 1);
      for (auto &l : vals) {
        if (l > 0 && l + 1 < n) {
          long long num_l = getnum(l);
          long long tol = getnum(l - 1);
          long long tor = getnum(l + 1);
          long long d1 = num_l - tol;
          long long d2 = num_l - tor;
          long long lg = min(abs(min(0ll, d1)), abs(min(0ll, d2)));
          long long rg = abs(min(0ll, d1)) + abs(min(0ll, d2));
          update(0, 1, 0, n - 1, l, lg);
          update(1, 1, 0, n - 1, l, rg);
        }
      }
    }
  }
}

### 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;
int n, q;
int a[100010];
pair<long long, int> tmin[2][4 * 100010];
long long ta[100010];
long long t[100010];
const long long inf = (long long)1e18 + 12345;
void update(int pos, long long val) {
  for (; pos < n; pos |= (pos + 1)) {
    t[pos] += val;
  }
}
long long getsum(int r) {
  long long result = 0;
  for (; r >= 0; r = (r & (r + 1)) - 1) {
    result += t[r];
  }
  return result;
}
long long getnum(int r) { return getsum(r); }
void update_ta(int pos, long long val) {
  for (; pos < n; pos |= (pos + 1)) {
    ta[pos] += val;
  }
}
long long get_ta(int r) {
  long long result = 0;
  for (; r >= 0; r = (r & (r + 1)) - 1) result += ta[r];
  return result;
}
long long get_ta(int l, int r) { return get_ta(r) - get_ta(l - 1); }
pair<long long, int> combine(pair<long long, int> lhs,
                             pair<long long, int> rhs) {
  if (lhs.first < rhs.first) return lhs;
  return rhs;
}
pair<long long, int> getmin(int t, int v, int vl, int vr, int l, int r) {
  if (l > vr || r < vl) return {inf, -1};
  if (l <= vl && vr <= r) return tmin[t][v];
  int vm = (vl + vr) >> 1;
  return combine(getmin(t, 2 * v, vl, vm, l, r),
                 getmin(t, 2 * v + 1, vm + 1, vr, l, r));
}
void update(int t, int v, int vl, int vr, int pos, long long val) {
  if (vl == vr) {
    tmin[t][v] = {val, pos};
    return;
  }
  int vm = (vl + vr) >> 1;
  if (pos <= vm)
    update(t, 2 * v, vl, vm, pos, val);
  else
    update(t, 2 * v + 1, vm + 1, vr, pos, val);
  tmin[t][v] = combine(tmin[t][2 * v], tmin[t][2 * v + 1]);
}
void build(int v, int vl, int vr) {
  if (vl == vr) {
    update(vl, a[vl]);
    update(vl + 1, -a[vl]);
    if (vl + 1 < n) {
      update_ta(vl, abs(a[vl] - a[vl + 1]));
    }
    if (vl > 0 && vr + 1 < n) {
      long long d1 = a[vl] - a[vl - 1];
      long long d2 = a[vr] - a[vr + 1];
      long long lg = min(abs(min(0ll, d1)), abs(min(0ll, d2)));
      long long rg = abs(min(0ll, d1)) + abs(min(0ll, d2));
      update(0, 1, 0, n - 1, vl, lg);
      update(1, 1, 0, n - 1, vl, rg);
    } else {
      update(0, 1, 0, n - 1, vl, inf);
      update(1, 1, 0, n - 1, vl, inf);
    }
    return;
  }
  int vm = (vl + vr) >> 1;
  build(2 * v, vl, vm);
  build(2 * v + 1, vm + 1, vr);
}
long long solve(int pos, int val) {
  long long oldnum = getnum(pos);
  long long left, right;
  if (pos > 0) {
    left = getnum(pos - 1);
    update_ta(pos - 1, abs(oldnum + val - left) - get_ta(pos - 1, pos - 1));
  }
  if (pos + 1 < n) {
    right = getnum(pos + 1);
    update_ta(pos, abs(oldnum + val - right) - get_ta(pos, pos));
  }
  long long result = get_ta(n - 1);
  if (pos > 0) {
    update_ta(pos - 1, abs(oldnum - left) - get_ta(pos - 1, pos - 1));
  }
  if (pos + 1 < n) {
    update_ta(pos, abs(oldnum - right) - get_ta(pos, pos));
  }
  return result;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  build(1, 0, n - 1);
  cin >> q;
  for (int i = 0; i < q; i++) {
    int t, l, r, x;
    cin >> t >> l >> r >> x;
    l--, r--;
    if (t == 1) {
      long long an = 0;
      if (l == 0) {
        an = max(an, solve(l, x));
        l++;
      }
      if (r + 1 == n) {
        an = max(an, solve(r, x));
        r--;
      }
      if (l <= r) {
        pair<long long, int> p = getmin(1, 1, 0, n - 1, l, r);
        if (p.first > x) p = getmin(0, 1, 0, n - 1, l, r);
        if (p.first > x) p.second = l;
        an = max(an, solve(p.second, x));
      }
      cout << an << '\n';
    } else {
      long long old_l = getnum(l);
      long long old_r = getnum(r);
      update(l, x);
      update(r + 1, -x);
      long long num_l = getnum(l);
      long long num_r = getnum(r);
      long long num_l_1, num_r_1;
      if (l > 0) {
        num_l_1 = getnum(l - 1);
        update_ta(l - 1, abs(num_l - num_l_1) - get_ta(l - 1, l - 1));
      }
      if (r + 1 < n) {
        num_r_1 = getnum(r + 1);
        update_ta(r, abs(num_r - num_r_1) - get_ta(r, r));
      }
      vector<int> vals;
      vals.push_back(l - 1);
      vals.push_back(l);
      vals.push_back(r);
      vals.push_back(r + 1);
      for (auto &l : vals) {
        if (l > 0 && l + 1 < n) {
          long long num_l = getnum(l);
          long long tol = getnum(l - 1);
          long long tor = getnum(l + 1);
          long long d1 = num_l - tol;
          long long d2 = num_l - tor;
          long long lg = min(abs(min(0ll, d1)), abs(min(0ll, d2)));
          long long rg = abs(min(0ll, d1)) + abs(min(0ll, d2));
          update(0, 1, 0, n - 1, l, lg);
          update(1, 1, 0, n - 1, l, rg);
        }
      }
    }
  }
}

```