#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")
const long long maxn = 1e5 + 10, maxm = 5e2 + 10, lg = 21, mod = 1e9 + 7,
                inf = 1e18;
long long n, q, sum = 0;
struct node {
  bool bb = 0;
  pair<long long, long long> p1 = {-inf, -inf}, p2 = {-inf, -inf};
} seg[maxn << 2];
long long laz[maxn << 2];
void add(long long l, long long r, long long x, long long s = 0,
         long long t = n, long long v = 1) {
  if (l >= t || r <= s) return;
  if (l <= s && r >= t) return void(laz[v] += x);
  add(l, r, x, s, ((s + t) >> 1), (v << 1));
  add(l, r, x, ((s + t) >> 1), t, ((v << 1) ^ 1));
}
long long get(long long id, long long s = 0, long long t = n, long long v = 1) {
  if (t - s == 1) return laz[v];
  return (id < ((s + t) >> 1) ? get(id, s, ((s + t) >> 1), (v << 1))
                              : (get(id, ((s + t) >> 1), t, ((v << 1) ^ 1)))) +
         laz[v];
}
node mrg(node l, node r) {
  node ret;
  if (l.bb || r.bb) {
    ret.bb = 1;
    return ret;
  }
  ret.p1 = max(l.p1, r.p1);
  ret.p2 = max(l.p2, r.p2);
  return ret;
}
void goz(long long id, pair<long long, long long> x, long long s = 0,
         long long t = n, long long v = 1) {
  if (t - s == 1) {
    seg[v] = node();
    if (x.first > x.second) swap(x.first, x.second);
    if (x.first >= 0 && x.second >= 0)
      seg[v].bb = 1;
    else if (x.first < 0 && x.second < 0)
      seg[v].p2 = x;
    else
      seg[v].p1 = x;
    return;
  }
  (id < ((s + t) >> 1) ? goz(id, x, s, ((s + t) >> 1), (v << 1))
                       : goz(id, x, ((s + t) >> 1), t, ((v << 1) ^ 1)));
  seg[v] = mrg(seg[(v << 1)], seg[((v << 1) ^ 1)]);
}
node weed(long long l, long long r, long long s = 0, long long t = n,
          long long v = 1) {
  if (l >= t || r <= s) return node();
  if (l <= s && r >= t) return seg[v];
  return mrg(weed(l, r, s, ((s + t) >> 1), (v << 1)),
             weed(l, r, ((s + t) >> 1), t, ((v << 1) ^ 1)));
}
long long X;
long long wat(long long e) { return abs(X + e) - abs(e); }
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  long long x, gx, ggx;
  cin >> ggx >> gx;
  sum += abs(gx - ggx);
  add(0, 1, ggx);
  for (int i = 2; i < n; i++) {
    cin >> x;
    sum += abs(x - gx);
    add(i - 1, i, gx);
    goz(i - 1, {gx - x, gx - ggx});
    ggx = gx, gx = x;
  }
  add(n - 1, n, x);
  cin >> q;
  while (q--) {
    long long ty, l, r;
    cin >> ty >> l >> r >> X;
    l--, r--;
    if (ty == 1) {
      long long ans = -inf;
      if (l == 0) ans = max(ans, wat(get(l) - get(l + 1))), l++;
      if (r == n - 1) ans = max(ans, wat(get(r) - get(r - 1))), r--;
      if (l <= r) {
        node it = weed(l, r + 1);
        if (it.bb)
          ans = 2 * X;
        else
          ans = max({ans, wat(it.p1.first) + wat(it.p1.second),
                     wat(it.p2.first) + wat(it.p2.second)});
      }
      cout << sum + ans << '\n';
    } else {
      if (l >= 1) sum += wat(get(l) - get(l - 1));
      if (r <= n - 2) sum += wat(get(r) - get(r + 1));
      add(l, r + 1, X);
      for (int i : {l, r, l - 1, r + 1})
        if (i >= 1 && i <= n - 2)
          goz(i, {get(i) - get(i - 1), get(i) - get(i + 1)});
    }
  }
  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;
#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")
const long long maxn = 1e5 + 10, maxm = 5e2 + 10, lg = 21, mod = 1e9 + 7,
                inf = 1e18;
long long n, q, sum = 0;
struct node {
  bool bb = 0;
  pair<long long, long long> p1 = {-inf, -inf}, p2 = {-inf, -inf};
} seg[maxn << 2];
long long laz[maxn << 2];
void add(long long l, long long r, long long x, long long s = 0,
         long long t = n, long long v = 1) {
  if (l >= t || r <= s) return;
  if (l <= s && r >= t) return void(laz[v] += x);
  add(l, r, x, s, ((s + t) >> 1), (v << 1));
  add(l, r, x, ((s + t) >> 1), t, ((v << 1) ^ 1));
}
long long get(long long id, long long s = 0, long long t = n, long long v = 1) {
  if (t - s == 1) return laz[v];
  return (id < ((s + t) >> 1) ? get(id, s, ((s + t) >> 1), (v << 1))
                              : (get(id, ((s + t) >> 1), t, ((v << 1) ^ 1)))) +
         laz[v];
}
node mrg(node l, node r) {
  node ret;
  if (l.bb || r.bb) {
    ret.bb = 1;
    return ret;
  }
  ret.p1 = max(l.p1, r.p1);
  ret.p2 = max(l.p2, r.p2);
  return ret;
}
void goz(long long id, pair<long long, long long> x, long long s = 0,
         long long t = n, long long v = 1) {
  if (t - s == 1) {
    seg[v] = node();
    if (x.first > x.second) swap(x.first, x.second);
    if (x.first >= 0 && x.second >= 0)
      seg[v].bb = 1;
    else if (x.first < 0 && x.second < 0)
      seg[v].p2 = x;
    else
      seg[v].p1 = x;
    return;
  }
  (id < ((s + t) >> 1) ? goz(id, x, s, ((s + t) >> 1), (v << 1))
                       : goz(id, x, ((s + t) >> 1), t, ((v << 1) ^ 1)));
  seg[v] = mrg(seg[(v << 1)], seg[((v << 1) ^ 1)]);
}
node weed(long long l, long long r, long long s = 0, long long t = n,
          long long v = 1) {
  if (l >= t || r <= s) return node();
  if (l <= s && r >= t) return seg[v];
  return mrg(weed(l, r, s, ((s + t) >> 1), (v << 1)),
             weed(l, r, ((s + t) >> 1), t, ((v << 1) ^ 1)));
}
long long X;
long long wat(long long e) { return abs(X + e) - abs(e); }
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  long long x, gx, ggx;
  cin >> ggx >> gx;
  sum += abs(gx - ggx);
  add(0, 1, ggx);
  for (int i = 2; i < n; i++) {
    cin >> x;
    sum += abs(x - gx);
    add(i - 1, i, gx);
    goz(i - 1, {gx - x, gx - ggx});
    ggx = gx, gx = x;
  }
  add(n - 1, n, x);
  cin >> q;
  while (q--) {
    long long ty, l, r;
    cin >> ty >> l >> r >> X;
    l--, r--;
    if (ty == 1) {
      long long ans = -inf;
      if (l == 0) ans = max(ans, wat(get(l) - get(l + 1))), l++;
      if (r == n - 1) ans = max(ans, wat(get(r) - get(r - 1))), r--;
      if (l <= r) {
        node it = weed(l, r + 1);
        if (it.bb)
          ans = 2 * X;
        else
          ans = max({ans, wat(it.p1.first) + wat(it.p1.second),
                     wat(it.p2.first) + wat(it.p2.second)});
      }
      cout << sum + ans << '\n';
    } else {
      if (l >= 1) sum += wat(get(l) - get(l - 1));
      if (r <= n - 2) sum += wat(get(r) - get(r + 1));
      add(l, r + 1, X);
      for (int i : {l, r, l - 1, r + 1})
        if (i >= 1 && i <= n - 2)
          goz(i, {get(i) - get(i - 1), get(i) - get(i + 1)});
    }
  }
  return 0;
}

```