#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
long long tree[maxn << 2];
long long a[maxn], ans;
int n;
void build(int i, int L, int R) {
  if (L == R) {
    if (L > 1) tree[i] = max(0ll, a[L - 1]) + max(0ll, -a[L]);
    return;
  }
  int MID = (L + R) >> 1;
  build(i << 1, L, MID);
  build(i << 1 | 1, MID + 1, R);
  tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
}
void update(int pos, long long x, int i, int L, int R) {
  if (L == R) {
    ans -= abs(a[pos]);
    a[pos] -= x;
    ans += abs(a[pos]);
    if (pos > 1) tree[i] = max(0ll, a[pos - 1]) + max(0ll, -a[pos]);
    if (x && pos < n - 1) update(pos + 1, 0, 1, 1, n - 1);
    return;
  }
  int MID = (L + R) >> 1;
  if (MID >= pos)
    update(pos, x, i << 1, L, MID);
  else
    update(pos, x, i << 1 | 1, MID + 1, R);
  tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
}
long long query(int l, int r, int i, int L, int R) {
  if (l <= L && R <= r) return tree[i];
  long long ans = 1e18;
  int MID = (L + R) >> 1;
  if (l <= MID) ans = min(ans, query(l, r, i << 1, L, MID));
  if (r > MID) ans = min(ans, query(l, r, i << 1 | 1, MID + 1, R));
  return ans;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  for (int i = 1; i < n; i++) {
    a[i] = a[i] - a[i + 1];
    ans += abs(a[i]);
  }
  build(1, 1, n - 1);
  int q;
  scanf("%d", &q);
  while (q--) {
    int t, l, r;
    long long x;
    scanf("%d%d%d%lld", &t, &l, &r, &x);
    if (t == 1) {
      if (l == r) {
        if (l == 1)
          printf("%lld\n", ans - abs(a[1]) + abs(a[1] + x));
        else if (l == n)
          printf("%lld\n", ans - abs(a[n - 1]) + abs(a[n - 1] - x));
        else {
          long long d =
              -abs(a[l]) + abs(a[l] + x) - abs(a[l - 1]) + abs(a[l - 1] - x);
          printf("%lld\n", ans + d);
        }
      } else {
        long long d = 0;
        if (l == 1) {
          d = max(d, -abs(a[l]) + abs(a[l] + x));
          ++l;
        }
        if (r == n) {
          d = max(d, -abs(a[r - 1]) + abs(a[r - 1] - x));
          --r;
        }
        d = max(d, 2 * x - 2 * query(l, r, 1, 1, n - 1));
        printf("%lld\n", ans + d);
      }
    } else {
      if (l > 1) update(l - 1, x, 1, 1, n - 1);
      if (r < n) update(r, -x, 1, 1, n - 1);
    }
  }
  return 0;
}

### Prompt

Please create a solution in CPP 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 + 7;
long long tree[maxn << 2];
long long a[maxn], ans;
int n;
void build(int i, int L, int R) {
  if (L == R) {
    if (L > 1) tree[i] = max(0ll, a[L - 1]) + max(0ll, -a[L]);
    return;
  }
  int MID = (L + R) >> 1;
  build(i << 1, L, MID);
  build(i << 1 | 1, MID + 1, R);
  tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
}
void update(int pos, long long x, int i, int L, int R) {
  if (L == R) {
    ans -= abs(a[pos]);
    a[pos] -= x;
    ans += abs(a[pos]);
    if (pos > 1) tree[i] = max(0ll, a[pos - 1]) + max(0ll, -a[pos]);
    if (x && pos < n - 1) update(pos + 1, 0, 1, 1, n - 1);
    return;
  }
  int MID = (L + R) >> 1;
  if (MID >= pos)
    update(pos, x, i << 1, L, MID);
  else
    update(pos, x, i << 1 | 1, MID + 1, R);
  tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
}
long long query(int l, int r, int i, int L, int R) {
  if (l <= L && R <= r) return tree[i];
  long long ans = 1e18;
  int MID = (L + R) >> 1;
  if (l <= MID) ans = min(ans, query(l, r, i << 1, L, MID));
  if (r > MID) ans = min(ans, query(l, r, i << 1 | 1, MID + 1, R));
  return ans;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  for (int i = 1; i < n; i++) {
    a[i] = a[i] - a[i + 1];
    ans += abs(a[i]);
  }
  build(1, 1, n - 1);
  int q;
  scanf("%d", &q);
  while (q--) {
    int t, l, r;
    long long x;
    scanf("%d%d%d%lld", &t, &l, &r, &x);
    if (t == 1) {
      if (l == r) {
        if (l == 1)
          printf("%lld\n", ans - abs(a[1]) + abs(a[1] + x));
        else if (l == n)
          printf("%lld\n", ans - abs(a[n - 1]) + abs(a[n - 1] - x));
        else {
          long long d =
              -abs(a[l]) + abs(a[l] + x) - abs(a[l - 1]) + abs(a[l - 1] - x);
          printf("%lld\n", ans + d);
        }
      } else {
        long long d = 0;
        if (l == 1) {
          d = max(d, -abs(a[l]) + abs(a[l] + x));
          ++l;
        }
        if (r == n) {
          d = max(d, -abs(a[r - 1]) + abs(a[r - 1] - x));
          --r;
        }
        d = max(d, 2 * x - 2 * query(l, r, 1, 1, n - 1));
        printf("%lld\n", ans + d);
      }
    } else {
      if (l > 1) update(l - 1, x, 1, 1, n - 1);
      if (r < n) update(r, -x, 1, 1, n - 1);
    }
  }
  return 0;
}

```