#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const long long inf = 1e17;
int n, qn, a[N];
long long b[N], ans;
inline long long Abs(long long x) { return x > 0 ? x : -x; }
long long cal(int x, int v) {
  return (x < 2 || x > n) ? 0 : (Abs(b[x] + v) - Abs(b[x]));
}
struct SegTree {
  long long val[N * 5];
  void change(int p, long long v, int l, int r, int x) {
    if (l == r) {
      val[x] = v;
      return;
    }
    int mid = (l + r) >> 1;
    if (p <= mid)
      change(p, v, l, mid, x << 1);
    else
      change(p, v, mid + 1, r, x << 1 | 1);
    val[x] = min(val[x << 1], val[x << 1 | 1]);
  }
  long long ask(int L, int R, int l, int r, int x) {
    if (L > R) return inf;
    if (l >= L && r <= R) return val[x];
    int mid = (l + r) >> 1;
    long long t = inf;
    if (L <= mid) t = min(t, ask(L, R, l, mid, x << 1));
    if (R > mid) t = min(t, ask(L, R, mid + 1, r, x << 1 | 1));
    return t;
  }
} A, B;
void up(int i) {
  if (i == 1 || i == n) return;
  if (b[i] < 0 && b[i + 1] > 0)
    B.change(i, i, 2, n - 1, 1), A.change(i, inf, 2, n - 1, 1);
  else
    A.change(i, max(0 - b[i], 0LL) + max(b[i + 1], 0LL), 2, n - 1, 1),
        B.change(i, inf, 2, n - 1, 1);
}
int main() {
  int i, j;
  scanf("%d", &n);
  for (i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (i = 2; i <= n; ++i) ans += Abs(b[i] = a[i] - a[i - 1]);
  for (i = 2; i < n; ++i) up(i);
  scanf("%d", &qn);
  for (; qn--;) {
    int t, l, r, x;
    scanf("%d%d%d%d", &t, &l, &r, &x);
    if (t == 1) {
      long long inc = -inf;
      if (l == 1) inc = max(inc, cal(2, -x)), ++l;
      if (r == n) inc = max(inc, cal(n, x)), --r;
      if (l <= r) {
        long long dec = A.ask(l, r, 2, n - 1, 1);
        if (dec != inf) inc = max(inc, 2LL * max(x - dec, 0LL));
        long long y = B.ask(l, r, 2, n - 1, 1);
        if (y != inf) inc = max(inc, cal(y, x) + cal(y + 1, -x));
      }
      printf("%I64d\n", ans + inc);
    } else {
      if (l != 1) ans += cal(l, x), b[l] += x, up(l - 1);
      if (r != n) ans += cal(r + 1, -x), b[r + 1] -= x, up(r + 1);
      up(l);
      if (l != r) up(r);
    }
  }
  return 0;
}

### Prompt

In Cpp, your task is to solve 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 N = 100005;
const long long inf = 1e17;
int n, qn, a[N];
long long b[N], ans;
inline long long Abs(long long x) { return x > 0 ? x : -x; }
long long cal(int x, int v) {
  return (x < 2 || x > n) ? 0 : (Abs(b[x] + v) - Abs(b[x]));
}
struct SegTree {
  long long val[N * 5];
  void change(int p, long long v, int l, int r, int x) {
    if (l == r) {
      val[x] = v;
      return;
    }
    int mid = (l + r) >> 1;
    if (p <= mid)
      change(p, v, l, mid, x << 1);
    else
      change(p, v, mid + 1, r, x << 1 | 1);
    val[x] = min(val[x << 1], val[x << 1 | 1]);
  }
  long long ask(int L, int R, int l, int r, int x) {
    if (L > R) return inf;
    if (l >= L && r <= R) return val[x];
    int mid = (l + r) >> 1;
    long long t = inf;
    if (L <= mid) t = min(t, ask(L, R, l, mid, x << 1));
    if (R > mid) t = min(t, ask(L, R, mid + 1, r, x << 1 | 1));
    return t;
  }
} A, B;
void up(int i) {
  if (i == 1 || i == n) return;
  if (b[i] < 0 && b[i + 1] > 0)
    B.change(i, i, 2, n - 1, 1), A.change(i, inf, 2, n - 1, 1);
  else
    A.change(i, max(0 - b[i], 0LL) + max(b[i + 1], 0LL), 2, n - 1, 1),
        B.change(i, inf, 2, n - 1, 1);
}
int main() {
  int i, j;
  scanf("%d", &n);
  for (i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (i = 2; i <= n; ++i) ans += Abs(b[i] = a[i] - a[i - 1]);
  for (i = 2; i < n; ++i) up(i);
  scanf("%d", &qn);
  for (; qn--;) {
    int t, l, r, x;
    scanf("%d%d%d%d", &t, &l, &r, &x);
    if (t == 1) {
      long long inc = -inf;
      if (l == 1) inc = max(inc, cal(2, -x)), ++l;
      if (r == n) inc = max(inc, cal(n, x)), --r;
      if (l <= r) {
        long long dec = A.ask(l, r, 2, n - 1, 1);
        if (dec != inf) inc = max(inc, 2LL * max(x - dec, 0LL));
        long long y = B.ask(l, r, 2, n - 1, 1);
        if (y != inf) inc = max(inc, cal(y, x) + cal(y + 1, -x));
      }
      printf("%I64d\n", ans + inc);
    } else {
      if (l != 1) ans += cal(l, x), b[l] += x, up(l - 1);
      if (r != n) ans += cal(r + 1, -x), b[r + 1] -= x, up(r + 1);
      up(l);
      if (l != r) up(r);
    }
  }
  return 0;
}

```