#include <bits/stdc++.h>
using namespace std;
const long long N = 500000 + 10;
const long long INF = 1e16;
struct Func {
  long long m, r;
  Func() { m = -INF, r = INF; }
  Func(long long m_, long long r_) { m = m_, r = r_; }
  long long get(long long x) { return max(max(-2 * x, m), 2 * x - r); }
  Func operator+(const Func &o) { return Func(max(m, o.m), min(r, o.r)); }
} nod[N];
long long n, q, a[N], b[N];
long long sum = 0;
void push_up(long long rt) { nod[rt] = nod[rt << 1] + nod[rt << 1 | 1]; }
void update(long long l, long long r, long long rt, long long pos, Func f) {
  if (l == r) {
    nod[rt] = f;
    return;
  }
  long long mid = (l + r) >> 1;
  if (mid >= pos)
    update(l, mid, rt << 1, pos, f);
  else
    update(mid + 1, r, rt << 1 | 1, pos, f);
  push_up(rt);
}
Func query(long long l, long long r, long long rt, long long L, long long R) {
  if (L <= l && r <= R) {
    return nod[rt];
  }
  long long mid = (l + r) >> 1;
  Func ans(-INF, INF);
  if (mid >= L) ans = ans + query(l, mid, rt << 1, L, R);
  if (mid < R) ans = ans + query(mid + 1, r, rt << 1 | 1, L, R);
  return ans;
}
Func generator(long long p, long long q) {
  p = -p, q = -q;
  long long m, r;
  if (p >= 0 && q >= 0) m = -2 * min(p, q), r = 2 * (p + q);
  if (p >= 0 && q <= 0) m = 0, r = 2 * p;
  if (p <= 0 && q >= 0) m = 0, r = 2 * q;
  if (p <= 0 && q <= 0) m = 0, r = 0;
  return Func(m, r);
}
int main() {
  scanf("%lld", &n);
  for (long long i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
  }
  for (long long i = 1; i < n; i++) {
    b[i] = a[i] - a[i + 1];
    sum += abs(b[i]);
  }
  for (long long i = 2; i < n; i++) {
    update(1, n, 1, i, generator(-b[i - 1], b[i]));
  }
  scanf("%lld", &q);
  while (q--) {
    long long op, l, r, x;
    scanf("%lld %lld %lld %lld", &op, &l, &r, &x);
    if (op == 2) {
      if (l > 1) {
        sum = sum - abs(b[l - 1]) + abs(b[l - 1] - x);
        b[l - 1] = b[l - 1] - x;
        update(1, n, 1, l, generator(-b[l - 1], b[l]));
        if (l > 2) update(1, n, 1, l - 1, generator(-b[l - 2], b[l - 1]));
      }
      if (r < n) {
        sum = sum - abs(b[r]) + abs(b[r] + x);
        b[r] = b[r] + x;
        update(1, n, 1, r, generator(-b[r - 1], b[r]));
        if (r < n - 1) update(1, n, 1, r + 1, generator(-b[r], b[r + 1]));
      }
    }
    if (op == 1) {
      long long ans = -INF;
      if (l == 1) {
        ans = max(ans, sum - abs(b[1]) + abs(b[1] + x));
        l++;
      }
      if (r == n) {
        ans = max(ans, sum - abs(b[n - 1]) + abs(b[n - 1] - x)), r--;
      }
      if (l <= r) {
        ans = max(ans, sum + query(1, n, 1, l, r).get(x));
      }
      printf("%lld\n", ans);
    }
  }
}

### Prompt

Your challenge is to write 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 long long N = 500000 + 10;
const long long INF = 1e16;
struct Func {
  long long m, r;
  Func() { m = -INF, r = INF; }
  Func(long long m_, long long r_) { m = m_, r = r_; }
  long long get(long long x) { return max(max(-2 * x, m), 2 * x - r); }
  Func operator+(const Func &o) { return Func(max(m, o.m), min(r, o.r)); }
} nod[N];
long long n, q, a[N], b[N];
long long sum = 0;
void push_up(long long rt) { nod[rt] = nod[rt << 1] + nod[rt << 1 | 1]; }
void update(long long l, long long r, long long rt, long long pos, Func f) {
  if (l == r) {
    nod[rt] = f;
    return;
  }
  long long mid = (l + r) >> 1;
  if (mid >= pos)
    update(l, mid, rt << 1, pos, f);
  else
    update(mid + 1, r, rt << 1 | 1, pos, f);
  push_up(rt);
}
Func query(long long l, long long r, long long rt, long long L, long long R) {
  if (L <= l && r <= R) {
    return nod[rt];
  }
  long long mid = (l + r) >> 1;
  Func ans(-INF, INF);
  if (mid >= L) ans = ans + query(l, mid, rt << 1, L, R);
  if (mid < R) ans = ans + query(mid + 1, r, rt << 1 | 1, L, R);
  return ans;
}
Func generator(long long p, long long q) {
  p = -p, q = -q;
  long long m, r;
  if (p >= 0 && q >= 0) m = -2 * min(p, q), r = 2 * (p + q);
  if (p >= 0 && q <= 0) m = 0, r = 2 * p;
  if (p <= 0 && q >= 0) m = 0, r = 2 * q;
  if (p <= 0 && q <= 0) m = 0, r = 0;
  return Func(m, r);
}
int main() {
  scanf("%lld", &n);
  for (long long i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
  }
  for (long long i = 1; i < n; i++) {
    b[i] = a[i] - a[i + 1];
    sum += abs(b[i]);
  }
  for (long long i = 2; i < n; i++) {
    update(1, n, 1, i, generator(-b[i - 1], b[i]));
  }
  scanf("%lld", &q);
  while (q--) {
    long long op, l, r, x;
    scanf("%lld %lld %lld %lld", &op, &l, &r, &x);
    if (op == 2) {
      if (l > 1) {
        sum = sum - abs(b[l - 1]) + abs(b[l - 1] - x);
        b[l - 1] = b[l - 1] - x;
        update(1, n, 1, l, generator(-b[l - 1], b[l]));
        if (l > 2) update(1, n, 1, l - 1, generator(-b[l - 2], b[l - 1]));
      }
      if (r < n) {
        sum = sum - abs(b[r]) + abs(b[r] + x);
        b[r] = b[r] + x;
        update(1, n, 1, r, generator(-b[r - 1], b[r]));
        if (r < n - 1) update(1, n, 1, r + 1, generator(-b[r], b[r + 1]));
      }
    }
    if (op == 1) {
      long long ans = -INF;
      if (l == 1) {
        ans = max(ans, sum - abs(b[1]) + abs(b[1] + x));
        l++;
      }
      if (r == n) {
        ans = max(ans, sum - abs(b[n - 1]) + abs(b[n - 1] - x)), r--;
      }
      if (l <= r) {
        ans = max(ans, sum + query(1, n, 1, l, r).get(x));
      }
      printf("%lld\n", ans);
    }
  }
}

```