#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const long long INF = 1e18;
int n, a[MAXN];
long long fen[MAXN];
long long seg2[MAXN << 2];
void add(int v, int val) {
  for (v++; v < MAXN; v += v & -v) fen[v] += val;
}
long long get(int v) {
  long long ret = 0;
  for (; v; v -= v & -v) ret += fen[v];
  return ret;
}
long long getVal(int i) { return get(i + 1) + a[i]; }
long long cal(int ind) {
  if (ind == 0 || ind == n - 1) return INF;
  long long x = getVal(ind - 1), y = getVal(ind), z = getVal(ind + 1);
  if (y >= min(x, z)) return max(0ll, max(x, z) - y);
  return max(x, z) - y + (min(x, z) - y);
}
void plant(int v, int b, int e) {
  if (e - b == 1) {
    seg2[v] = cal(b);
    return;
  }
  int mid = b + e >> 1;
  plant(v << 1, b, mid);
  plant(v << 1 ^ 1, mid, e);
  seg2[v] = min(seg2[v << 1], seg2[v << 1 ^ 1]);
}
void update(int v, int b, int e, int pos) {
  if (e - b == 1) {
    seg2[v] = cal(b);
    return;
  }
  int mid = b + e >> 1;
  if (pos < mid)
    update(v << 1, b, mid, pos);
  else
    update(v << 1 ^ 1, mid, e, pos);
  seg2[v] = min(seg2[v << 1], seg2[v << 1 ^ 1]);
}
long long _get2(int v, int b, int e, int l, int r) {
  if (l <= b && e <= r) return seg2[v];
  if (r <= b || e <= l) return INF;
  int mid = b + e >> 1;
  return min(_get2(v << 1, b, mid, l, r), _get2(v << 1 ^ 1, mid, e, l, r));
}
long long ans = 0;
long long check(int ind, int x) {
  long long ret = ans;
  if (ind - 1 >= 0) ret -= abs(getVal(ind - 1) - getVal(ind));
  if (ind + 1 < n) ret -= abs(getVal(ind) - getVal(ind + 1));
  if (ind - 1 >= 0) ret += abs(getVal(ind - 1) - (getVal(ind) + x));
  if (ind + 1 < n) ret += abs((getVal(ind) + x) - getVal(ind + 1));
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> a[i], ans += (i ? abs(a[i] - a[i - 1]) : 0);
  plant(1, 0, n - 1);
  int q;
  cin >> q;
  while (q--) {
    int t, l, r, x;
    cin >> t >> l >> r >> x, l--;
    if (t == 1) {
      long long res = max(check(l, x), check(r - 1, x));
      if (r - l > 2) {
        long long y = _get2(1, 0, n - 1, l + 1, r - 1);
        if (x > y) res = max(res, ans + (x - y) * 2ll);
      }
      cout << res << "\n";
    } else {
      for (int i = max(0, l - 1); i <= l && i + 1 < n; i++)
        ans -= abs(getVal(i) - getVal(i + 1));
      for (int i = max(l + 1, r - 2); i <= r - 1 && i + 1 < n; i++)
        ans -= abs(getVal(i) - getVal(i + 1));
      add(l, x);
      add(r, -x);
      for (int i = max(0, l - 1); i <= l && i + 1 < n; i++)
        ans += abs(getVal(i) - getVal(i + 1));
      for (int i = max(l + 1, r - 2); i <= r - 1 && i + 1 < n; i++)
        ans += abs(getVal(i) - getVal(i + 1));
      for (int i = max(0, l - 1); i <= min(n - 1, l + 1); i++)
        update(1, 0, n - 1, i);
      for (int i = max(0, r - 2); i <= min(n - 1, r); i++)
        update(1, 0, n - 1, i);
    }
  }
  return 0;
}

### Prompt

Your challenge is to write 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;
const int MAXN = 1e5 + 10;
const long long INF = 1e18;
int n, a[MAXN];
long long fen[MAXN];
long long seg2[MAXN << 2];
void add(int v, int val) {
  for (v++; v < MAXN; v += v & -v) fen[v] += val;
}
long long get(int v) {
  long long ret = 0;
  for (; v; v -= v & -v) ret += fen[v];
  return ret;
}
long long getVal(int i) { return get(i + 1) + a[i]; }
long long cal(int ind) {
  if (ind == 0 || ind == n - 1) return INF;
  long long x = getVal(ind - 1), y = getVal(ind), z = getVal(ind + 1);
  if (y >= min(x, z)) return max(0ll, max(x, z) - y);
  return max(x, z) - y + (min(x, z) - y);
}
void plant(int v, int b, int e) {
  if (e - b == 1) {
    seg2[v] = cal(b);
    return;
  }
  int mid = b + e >> 1;
  plant(v << 1, b, mid);
  plant(v << 1 ^ 1, mid, e);
  seg2[v] = min(seg2[v << 1], seg2[v << 1 ^ 1]);
}
void update(int v, int b, int e, int pos) {
  if (e - b == 1) {
    seg2[v] = cal(b);
    return;
  }
  int mid = b + e >> 1;
  if (pos < mid)
    update(v << 1, b, mid, pos);
  else
    update(v << 1 ^ 1, mid, e, pos);
  seg2[v] = min(seg2[v << 1], seg2[v << 1 ^ 1]);
}
long long _get2(int v, int b, int e, int l, int r) {
  if (l <= b && e <= r) return seg2[v];
  if (r <= b || e <= l) return INF;
  int mid = b + e >> 1;
  return min(_get2(v << 1, b, mid, l, r), _get2(v << 1 ^ 1, mid, e, l, r));
}
long long ans = 0;
long long check(int ind, int x) {
  long long ret = ans;
  if (ind - 1 >= 0) ret -= abs(getVal(ind - 1) - getVal(ind));
  if (ind + 1 < n) ret -= abs(getVal(ind) - getVal(ind + 1));
  if (ind - 1 >= 0) ret += abs(getVal(ind - 1) - (getVal(ind) + x));
  if (ind + 1 < n) ret += abs((getVal(ind) + x) - getVal(ind + 1));
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> a[i], ans += (i ? abs(a[i] - a[i - 1]) : 0);
  plant(1, 0, n - 1);
  int q;
  cin >> q;
  while (q--) {
    int t, l, r, x;
    cin >> t >> l >> r >> x, l--;
    if (t == 1) {
      long long res = max(check(l, x), check(r - 1, x));
      if (r - l > 2) {
        long long y = _get2(1, 0, n - 1, l + 1, r - 1);
        if (x > y) res = max(res, ans + (x - y) * 2ll);
      }
      cout << res << "\n";
    } else {
      for (int i = max(0, l - 1); i <= l && i + 1 < n; i++)
        ans -= abs(getVal(i) - getVal(i + 1));
      for (int i = max(l + 1, r - 2); i <= r - 1 && i + 1 < n; i++)
        ans -= abs(getVal(i) - getVal(i + 1));
      add(l, x);
      add(r, -x);
      for (int i = max(0, l - 1); i <= l && i + 1 < n; i++)
        ans += abs(getVal(i) - getVal(i + 1));
      for (int i = max(l + 1, r - 2); i <= r - 1 && i + 1 < n; i++)
        ans += abs(getVal(i) - getVal(i + 1));
      for (int i = max(0, l - 1); i <= min(n - 1, l + 1); i++)
        update(1, 0, n - 1, i);
      for (int i = max(0, r - 2); i <= min(n - 1, r); i++)
        update(1, 0, n - 1, i);
    }
  }
  return 0;
}

```