#include <bits/stdc++.h>
using namespace std;
long long ans, a[100010], b[100010];
int n;
long long seg[100010 << 2];
void push_up(int o) { seg[o] = min(seg[o << 1], seg[o << 1 | 1]); }
void build(int l, int r, int o) {
  if (l == r) {
    seg[o] = b[l];
    return;
  }
  int m = (l + r) >> 1;
  build(l, m, o << 1), build(m + 1, r, o << 1 | 1);
  push_up(o);
}
void update(int l, int r, int o, int v, long long x) {
  if (l == r) {
    seg[o] = x;
    return;
  }
  int m = (l + r) >> 1;
  if (v <= m)
    update(l, m, o << 1, v, x);
  else
    update(m + 1, r, o << 1 | 1, v, x);
  push_up(o);
}
long long query(int l, int r, int o, int ql, int qr) {
  if (ql <= l && r <= qr) return seg[o];
  int m = (l + r) >> 1;
  if (qr <= m) return query(l, m, o << 1, ql, qr);
  if (ql > m) return query(m + 1, r, o << 1 | 1, ql, qr);
  return min(query(l, m, o << 1, ql, m),
             query(m + 1, r, o << 1 | 1, m + 1, qr));
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  for (int i = n; i >= 1; i--) a[i] -= a[i - 1];
  for (int i = 2; i <= n; i++) ans += abs(a[i]);
  for (int i = 1; i <= n; i++) b[i] = max(a[i + 1], 0ll) + max(-a[i], 0ll);
  build(1, n, 1);
  int q;
  scanf("%d", &q);
  while (q--) {
    int type, l, r;
    long long x;
    scanf("%d%d%d%lld", &type, &l, &r, &x);
    if (type == 1) {
      if (l == r) {
        if (l == n)
          printf("%lld\n", ans - abs(a[n]) + abs(a[n] + x));
        else {
          long long tmp = ans;
          tmp -= (abs(a[l]) + abs(a[l + 1]));
          tmp += (abs(a[l] + x) + abs(a[l + 1] - x));
          printf("%lld\n", tmp);
        }
      } else {
        long long s = query(1, n, 1, l, r);
        s = min(s, x);
        printf("%lld\n", ans + (x - s) * 2);
      }
    } else {
      ans -= (abs(a[l]) + abs(a[r + 1]));
      a[l] += x, a[r + 1] -= x;
      ans += (abs(a[l]) + abs(a[r + 1]));
      update(1, n, 1, l, max(a[l + 1], 0ll) + max(-a[l], 0ll));
      if (l > 1) update(1, n, 1, l - 1, max(a[l], 0ll) + max(-a[l - 1], 0ll));
      update(1, n, 1, r, max(a[r + 1], 0ll) + max(-a[r], 0ll));
      if (r < n)
        update(1, n, 1, r + 1, max(a[r + 2], 0ll) + max(-a[r + 1], 0ll));
    }
  }
  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;
long long ans, a[100010], b[100010];
int n;
long long seg[100010 << 2];
void push_up(int o) { seg[o] = min(seg[o << 1], seg[o << 1 | 1]); }
void build(int l, int r, int o) {
  if (l == r) {
    seg[o] = b[l];
    return;
  }
  int m = (l + r) >> 1;
  build(l, m, o << 1), build(m + 1, r, o << 1 | 1);
  push_up(o);
}
void update(int l, int r, int o, int v, long long x) {
  if (l == r) {
    seg[o] = x;
    return;
  }
  int m = (l + r) >> 1;
  if (v <= m)
    update(l, m, o << 1, v, x);
  else
    update(m + 1, r, o << 1 | 1, v, x);
  push_up(o);
}
long long query(int l, int r, int o, int ql, int qr) {
  if (ql <= l && r <= qr) return seg[o];
  int m = (l + r) >> 1;
  if (qr <= m) return query(l, m, o << 1, ql, qr);
  if (ql > m) return query(m + 1, r, o << 1 | 1, ql, qr);
  return min(query(l, m, o << 1, ql, m),
             query(m + 1, r, o << 1 | 1, m + 1, qr));
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  for (int i = n; i >= 1; i--) a[i] -= a[i - 1];
  for (int i = 2; i <= n; i++) ans += abs(a[i]);
  for (int i = 1; i <= n; i++) b[i] = max(a[i + 1], 0ll) + max(-a[i], 0ll);
  build(1, n, 1);
  int q;
  scanf("%d", &q);
  while (q--) {
    int type, l, r;
    long long x;
    scanf("%d%d%d%lld", &type, &l, &r, &x);
    if (type == 1) {
      if (l == r) {
        if (l == n)
          printf("%lld\n", ans - abs(a[n]) + abs(a[n] + x));
        else {
          long long tmp = ans;
          tmp -= (abs(a[l]) + abs(a[l + 1]));
          tmp += (abs(a[l] + x) + abs(a[l + 1] - x));
          printf("%lld\n", tmp);
        }
      } else {
        long long s = query(1, n, 1, l, r);
        s = min(s, x);
        printf("%lld\n", ans + (x - s) * 2);
      }
    } else {
      ans -= (abs(a[l]) + abs(a[r + 1]));
      a[l] += x, a[r + 1] -= x;
      ans += (abs(a[l]) + abs(a[r + 1]));
      update(1, n, 1, l, max(a[l + 1], 0ll) + max(-a[l], 0ll));
      if (l > 1) update(1, n, 1, l - 1, max(a[l], 0ll) + max(-a[l - 1], 0ll));
      update(1, n, 1, r, max(a[r + 1], 0ll) + max(-a[r], 0ll));
      if (r < n)
        update(1, n, 1, r + 1, max(a[r + 2], 0ll) + max(-a[r + 1], 0ll));
    }
  }
  return 0;
}

```