#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
const long long INFLL = 0x3f3f3f3f3f3f3f3fll;
const int MAXN = 2e5 + 5;
const int mod = 1e9 + 7;
int a[MAXN];
long long d[MAXN];
long long tree[MAXN * 4];
long long query(int id, int l, int r, int L, int R) {
  if (L <= l && R >= r) {
    return tree[id];
  }
  int mid = (l + r) >> 1;
  long long ret = -INFLL;
  if (L <= mid) ret = max(ret, query(id << 1, l, mid, L, R));
  if (R > mid) ret = max(ret, query(id << 1 | 1, mid + 1, r, L, R));
  return ret;
}
void update(int id, int l, int r, int x, long long v) {
  if (l == r) {
    tree[id] = v;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    update(id << 1, l, mid, x, v);
  else
    update(id << 1 | 1, mid + 1, r, x, v);
  tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
}
int main() {
  int n;
  cin >> n;
  long long ans = 0;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i < n; i++) {
    d[i] = a[i + 1] - a[i];
    ans = (ans + abs(d[i]));
  }
  for (int i = 1; i <= n; i++)
    update(1, 1, n, i, min(d[i - 1], 0LL) + min(-d[i], 0LL));
  int q;
  cin >> q;
  1;
  while (q--) {
    int op, l, r, x;
    scanf("%d %d %d %d", &op, &l, &r, &x);
    if (op == 1) {
      if (l == r)
        printf("%lld\n", ans +
                             (l == 1 ? 0 : abs(d[l - 1] + x) - abs(d[l - 1])) +
                             (l == n ? 0 : -abs(d[l]) + abs(d[l] - x)));
      else {
        printf("%lld\n", ans + max(2 * (x + query(1, 1, n, l, r)), 0LL));
        1;
      }
    } else {
      if (l > 1) {
        ans -= abs(d[l - 1]);
        d[l - 1] += x;
        update(1, 1, n, l - 1, min(d[l - 2], 0LL) + min(-d[l - 1], 0LL));
        update(1, 1, n, l, min(d[l - 1], 0LL) + min(-d[l], 0LL));
        ans += abs(d[l - 1]);
      }
      if (r < n) {
        ans -= abs(d[r]);
        d[r] -= x;
        update(1, 1, n, r, min(d[r - 1], 0LL) + min(-d[r], 0LL));
        update(1, 1, n, r + 1, min(d[r], 0LL) + min(-d[r + 1], 0LL));
        ans += abs(d[r]);
      }
    }
  }
  return 0;
}

### Prompt

Generate 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 MOD = 1e9 + 7;
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
const long long INFLL = 0x3f3f3f3f3f3f3f3fll;
const int MAXN = 2e5 + 5;
const int mod = 1e9 + 7;
int a[MAXN];
long long d[MAXN];
long long tree[MAXN * 4];
long long query(int id, int l, int r, int L, int R) {
  if (L <= l && R >= r) {
    return tree[id];
  }
  int mid = (l + r) >> 1;
  long long ret = -INFLL;
  if (L <= mid) ret = max(ret, query(id << 1, l, mid, L, R));
  if (R > mid) ret = max(ret, query(id << 1 | 1, mid + 1, r, L, R));
  return ret;
}
void update(int id, int l, int r, int x, long long v) {
  if (l == r) {
    tree[id] = v;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    update(id << 1, l, mid, x, v);
  else
    update(id << 1 | 1, mid + 1, r, x, v);
  tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
}
int main() {
  int n;
  cin >> n;
  long long ans = 0;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i < n; i++) {
    d[i] = a[i + 1] - a[i];
    ans = (ans + abs(d[i]));
  }
  for (int i = 1; i <= n; i++)
    update(1, 1, n, i, min(d[i - 1], 0LL) + min(-d[i], 0LL));
  int q;
  cin >> q;
  1;
  while (q--) {
    int op, l, r, x;
    scanf("%d %d %d %d", &op, &l, &r, &x);
    if (op == 1) {
      if (l == r)
        printf("%lld\n", ans +
                             (l == 1 ? 0 : abs(d[l - 1] + x) - abs(d[l - 1])) +
                             (l == n ? 0 : -abs(d[l]) + abs(d[l] - x)));
      else {
        printf("%lld\n", ans + max(2 * (x + query(1, 1, n, l, r)), 0LL));
        1;
      }
    } else {
      if (l > 1) {
        ans -= abs(d[l - 1]);
        d[l - 1] += x;
        update(1, 1, n, l - 1, min(d[l - 2], 0LL) + min(-d[l - 1], 0LL));
        update(1, 1, n, l, min(d[l - 1], 0LL) + min(-d[l], 0LL));
        ans += abs(d[l - 1]);
      }
      if (r < n) {
        ans -= abs(d[r]);
        d[r] -= x;
        update(1, 1, n, r, min(d[r - 1], 0LL) + min(-d[r], 0LL));
        update(1, 1, n, r + 1, min(d[r], 0LL) + min(-d[r + 1], 0LL));
        ans += abs(d[r]);
      }
    }
  }
  return 0;
}

```