#include <bits/stdc++.h>
using namespace std;
const long long MAX = (1 << 30);
const long long N = 100005;
long long n, q;
struct qq {
  long long l, r;
  long long s1, s2;
  long long c, sum;
  long long a[4];
} tr[N * 2];
long long num;
long long a[N];
void renovate(long long *a, long long x, long long y) {
  a[0] = max(a[0], x + y - abs(x) - abs(y));
  a[1] = max(a[1], x - y - abs(x) - abs(y));
  a[2] = max(a[2], y - x - abs(x) - abs(y));
  a[3] = max(a[3], -x - y - abs(x) - abs(y));
}
void update(long long now) {
  long long s1 = tr[now].s1, s2 = tr[now].s2;
  long long x = a[tr[s1].r], y = a[tr[s2].l];
  tr[now].sum = tr[s1].sum + tr[s2].sum;
  for (long long u = 0; u < 4; u++)
    tr[now].a[u] = max(tr[s1].a[u], tr[s2].a[u]);
  renovate(tr[now].a, x, y);
}
void bt(long long l, long long r) {
  long long A = ++num;
  tr[A].l = l;
  tr[A].r = r;
  if (l == r) {
    tr[A].c = a[l];
    tr[A].sum = abs(a[l]);
    memset(tr[A].a, -63, sizeof(tr[A].a));
    return;
  }
  long long mid = (l + r) >> 1;
  tr[A].s1 = num + 1;
  bt(l, mid);
  tr[A].s2 = num + 1;
  bt(mid + 1, r);
  update(A);
}
void change(long long now, long long x) {
  if (tr[now].l == tr[now].r) {
    tr[now].c = a[tr[now].l];
    tr[now].sum = abs(a[tr[now].l]);
    return;
  }
  long long mid = (tr[now].l + tr[now].r) >> 1;
  long long s1 = tr[now].s1, s2 = tr[now].s2;
  if (x <= mid)
    change(s1, x);
  else
    change(s2, x);
  update(now);
}
long long ans[4];
void get(long long now, long long l, long long r) {
  if (tr[now].l == l && tr[now].r == r) {
    for (long long u = 0; u < 4; u++) ans[u] = max(ans[u], tr[now].a[u]);
    return;
  }
  long long s1 = tr[now].s1, s2 = tr[now].s2;
  long long mid = (tr[now].l + tr[now].r) >> 1;
  if (r <= mid)
    get(s1, l, r);
  else if (l > mid)
    get(s2, l, r);
  else {
    get(s1, l, mid);
    get(s2, mid + 1, r);
    long long x = a[tr[s1].r], y = a[tr[s2].l];
    renovate(ans, x, y);
  }
}
int main() {
  scanf("%I64d", &n);
  for (long long u = 1; u <= n; u++) scanf("%I64d", &a[u]);
  n--;
  for (long long u = 1; u <= n; u++) a[u] = a[u] - a[u + 1];
  bt(1, n);
  scanf("%I64d", &q);
  for (long long u = 1; u <= q; u++) {
    long long op, l, r, x;
    scanf("%I64d%I64d%I64d%I64d", &op, &l, &r, &x);
    if (op == 2) {
      if (l != 1) {
        a[l - 1] -= x;
        change(1, l - 1);
      }
      if (r <= n) {
        a[r] += x;
        change(1, r);
      }
    } else {
      memset(ans, -63, sizeof(ans));
      get(1, max(1LL, l - 1), min(n, r));
      long long lalal = ans[0];
      lalal = max(lalal, ans[1] - 2 * x);
      lalal = max(lalal, ans[2] + 2 * x);
      lalal = max(lalal, ans[3]);
      printf("%I64d\n", tr[1].sum + lalal);
    }
  }
  return 0;
}

### Prompt

Create a solution in CPP for 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 long long MAX = (1 << 30);
const long long N = 100005;
long long n, q;
struct qq {
  long long l, r;
  long long s1, s2;
  long long c, sum;
  long long a[4];
} tr[N * 2];
long long num;
long long a[N];
void renovate(long long *a, long long x, long long y) {
  a[0] = max(a[0], x + y - abs(x) - abs(y));
  a[1] = max(a[1], x - y - abs(x) - abs(y));
  a[2] = max(a[2], y - x - abs(x) - abs(y));
  a[3] = max(a[3], -x - y - abs(x) - abs(y));
}
void update(long long now) {
  long long s1 = tr[now].s1, s2 = tr[now].s2;
  long long x = a[tr[s1].r], y = a[tr[s2].l];
  tr[now].sum = tr[s1].sum + tr[s2].sum;
  for (long long u = 0; u < 4; u++)
    tr[now].a[u] = max(tr[s1].a[u], tr[s2].a[u]);
  renovate(tr[now].a, x, y);
}
void bt(long long l, long long r) {
  long long A = ++num;
  tr[A].l = l;
  tr[A].r = r;
  if (l == r) {
    tr[A].c = a[l];
    tr[A].sum = abs(a[l]);
    memset(tr[A].a, -63, sizeof(tr[A].a));
    return;
  }
  long long mid = (l + r) >> 1;
  tr[A].s1 = num + 1;
  bt(l, mid);
  tr[A].s2 = num + 1;
  bt(mid + 1, r);
  update(A);
}
void change(long long now, long long x) {
  if (tr[now].l == tr[now].r) {
    tr[now].c = a[tr[now].l];
    tr[now].sum = abs(a[tr[now].l]);
    return;
  }
  long long mid = (tr[now].l + tr[now].r) >> 1;
  long long s1 = tr[now].s1, s2 = tr[now].s2;
  if (x <= mid)
    change(s1, x);
  else
    change(s2, x);
  update(now);
}
long long ans[4];
void get(long long now, long long l, long long r) {
  if (tr[now].l == l && tr[now].r == r) {
    for (long long u = 0; u < 4; u++) ans[u] = max(ans[u], tr[now].a[u]);
    return;
  }
  long long s1 = tr[now].s1, s2 = tr[now].s2;
  long long mid = (tr[now].l + tr[now].r) >> 1;
  if (r <= mid)
    get(s1, l, r);
  else if (l > mid)
    get(s2, l, r);
  else {
    get(s1, l, mid);
    get(s2, mid + 1, r);
    long long x = a[tr[s1].r], y = a[tr[s2].l];
    renovate(ans, x, y);
  }
}
int main() {
  scanf("%I64d", &n);
  for (long long u = 1; u <= n; u++) scanf("%I64d", &a[u]);
  n--;
  for (long long u = 1; u <= n; u++) a[u] = a[u] - a[u + 1];
  bt(1, n);
  scanf("%I64d", &q);
  for (long long u = 1; u <= q; u++) {
    long long op, l, r, x;
    scanf("%I64d%I64d%I64d%I64d", &op, &l, &r, &x);
    if (op == 2) {
      if (l != 1) {
        a[l - 1] -= x;
        change(1, l - 1);
      }
      if (r <= n) {
        a[r] += x;
        change(1, r);
      }
    } else {
      memset(ans, -63, sizeof(ans));
      get(1, max(1LL, l - 1), min(n, r));
      long long lalal = ans[0];
      lalal = max(lalal, ans[1] - 2 * x);
      lalal = max(lalal, ans[2] + 2 * x);
      lalal = max(lalal, ans[3]);
      printf("%I64d\n", tr[1].sum + lalal);
    }
  }
  return 0;
}

```