#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const long long maxn = 1e5 + 100;
const long long mod = 1e9 + 7;
const long double PI = acos((long double)-1);
long long pw(long long a, long long b, long long md = mod) {
  long long res = 1;
  while (b) {
    if (b & 1) {
      res = (a * res) % md;
    }
    a = (a * a) % md;
    b >>= 1;
  }
  return (res);
}
long long n, q;
long long a[maxn];
long long diff[maxn];
long long ans = 0;
struct BIT {
  long long fen[maxn];
  void add(long long x, long long pos) {
    for (; pos < maxn; pos += pos & -pos) fen[pos] += x;
  }
  void add(long long x, long long l, long long r) {
    add(x, l);
    add(-x, r + 1);
  }
  long long get(long long pos) {
    long long ans = 0;
    for (; pos; pos -= pos & -pos) ans += fen[pos];
    return (ans);
  }
  long long get(long long l, long long r) { return (get(r) - get(l - 1)); }
};
BIT fen;
struct segment {
  long long seg[maxn * 4];
  long long peak[maxn * 4];
  long long valley[maxn * 4];
  segment(long long x) {
    memset(seg, x, sizeof seg);
    memset(valley, x, sizeof valley);
  }
  void build(long long v = 1, long long l = 1, long long r = n + 1) {
    if (r - l == 1) {
      if (l == 1 or l == n) return;
      if (a[l - 1] > a[l] and a[l] < a[l + 1])
        valley[v] = l;
      else
        seg[v] = max(a[l + 1] - a[l], a[l - 1] - a[l]);
      if (a[l - 1] <= a[l] and a[l] >= a[l + 1]) peak[v] = l;
      return;
    }
    long long mid = (l + r) / 2;
    build(2 * v, l, mid);
    build(2 * v + 1, mid, r);
    seg[v] = min(seg[2 * v], seg[2 * v + 1]);
    peak[v] = max(peak[2 * v], peak[2 * v + 1]);
    valley[v] = min(valley[2 * v], valley[2 * v + 1]);
  }
  void update(long long pos, long long x, long long st, long long v = 1,
              long long l = 1, long long r = n + 1) {
    if (r - l == 1) {
      if (st == 1) peak[v] = x;
      if (st == 2) valley[v] = x;
      if (st == 3) seg[v] = x;
      return;
    }
    long long mid = (l + r) / 2;
    if (pos < mid)
      update(pos, x, st, 2 * v, l, mid);
    else
      update(pos, x, st, 2 * v + 1, mid, r);
    seg[v] = min(seg[2 * v], seg[2 * v + 1]);
    peak[v] = max(peak[2 * v], peak[2 * v + 1]);
    valley[v] = min(valley[2 * v], valley[2 * v + 1]);
  }
  long long pek(long long L, long long R, long long v = 1, long long l = 1,
                long long r = n + 1) {
    if (r <= L or R <= l) return (0);
    if (L <= l and r <= R) return (peak[v]);
    long long mid = (l + r) / 2;
    return (max(pek(L, R, 2 * v, l, mid), pek(L, R, 2 * v + 1, mid, r)));
  }
  long long query(long long L, long long R, long long v = 1, long long l = 1,
                  long long r = n + 1) {
    if (r <= L or R <= l) return (seg[n * 4 + 1]);
    if (L <= l and r <= R) return (seg[v]);
    long long mid = (l + r) / 2;
    return (min(query(L, R, 2 * v, l, mid), query(L, R, 2 * v + 1, mid, r)));
  }
  long long valy(long long L, long long R, long long v = 1, long long l = 1,
                 long long r = n + 1) {
    if (r <= L or R <= l) return (seg[n * 4 + 1]);
    if (L <= l and r <= R) return (valley[v]);
    long long mid = (l + r) / 2;
    return (min(valy(L, R, 2 * v, l, mid), valy(L, R, 2 * v + 1, mid, r)));
  }
  long long solve(long long l, long long r, long long x) {
    if (pek(l, r)) return (2 * x);
    long long ans = -seg[n * 4 + 1];
    long long res = query(l, r);
    if (res < seg[n * 4 + 1]) ans = max(0LL, (x - res) * 2);
    res = valy(l, r);
    if (res < seg[n * 4 + 1])
      ans = max(ans, ((x < diff[res]) ? -x : x - diff[res] * 2) +
                         ((x < diff[res - 1]) ? -x : x - diff[res - 1] * 2));
    if (l == 1) ans = max(ans, abs(fen.get(1) + x - fen.get(2)) - diff[1]);
    if (r == n + 1)
      ans = max(ans, abs(fen.get(n) + x - fen.get(n - 1)) - diff[n - 1]);
    return (ans);
  }
};
segment seg(63);
void calc(long long pos) {
  if (pos < n) {
    long long b = fen.get(pos);
    long long c = fen.get(pos + 1);
    if (pos > 1) {
      long long a = fen.get(pos - 1);
      if (a <= b and b >= c) {
        seg.update(pos, pos, 1);
      } else {
        seg.update(pos, 0, 1);
      }
      if (a > b and b < c) {
        seg.update(pos, pos, 2);
        seg.update(pos, seg.seg[n * 4 + 1], 3);
      } else {
        seg.update(pos, seg.seg[n * 4 + 1], 2);
        seg.update(pos, max(c - b, a - b), 3);
      }
    }
    ans += abs(b - c) - diff[pos];
    diff[pos] = abs(b - c);
  }
}
void update(long long l, long long r, long long x) {
  fen.add(x, l, r);
  calc(l);
  if (l > 1) calc(l - 1);
  if (r != l) calc(r);
  if (r < n) calc(r + 1);
}
int32_t main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n;
  for (long long i = 1; i <= n; i++) cin >> a[i], fen.add(a[i], i, i);
  for (long long i = 1; i < n; i++)
    diff[i] = abs(a[i] - a[i + 1]), ans += diff[i];
  seg.build();
  cin >> q;
  while (q--) {
    long long t, l, r, x;
    cin >> t >> l >> r >> x;
    if (t == 1)
      cout << ans + seg.solve(l, r + 1, x) << '\n';
    else
      update(l, r, x);
  }
  return (0);
}

### Prompt

Your task is to create 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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const long long maxn = 1e5 + 100;
const long long mod = 1e9 + 7;
const long double PI = acos((long double)-1);
long long pw(long long a, long long b, long long md = mod) {
  long long res = 1;
  while (b) {
    if (b & 1) {
      res = (a * res) % md;
    }
    a = (a * a) % md;
    b >>= 1;
  }
  return (res);
}
long long n, q;
long long a[maxn];
long long diff[maxn];
long long ans = 0;
struct BIT {
  long long fen[maxn];
  void add(long long x, long long pos) {
    for (; pos < maxn; pos += pos & -pos) fen[pos] += x;
  }
  void add(long long x, long long l, long long r) {
    add(x, l);
    add(-x, r + 1);
  }
  long long get(long long pos) {
    long long ans = 0;
    for (; pos; pos -= pos & -pos) ans += fen[pos];
    return (ans);
  }
  long long get(long long l, long long r) { return (get(r) - get(l - 1)); }
};
BIT fen;
struct segment {
  long long seg[maxn * 4];
  long long peak[maxn * 4];
  long long valley[maxn * 4];
  segment(long long x) {
    memset(seg, x, sizeof seg);
    memset(valley, x, sizeof valley);
  }
  void build(long long v = 1, long long l = 1, long long r = n + 1) {
    if (r - l == 1) {
      if (l == 1 or l == n) return;
      if (a[l - 1] > a[l] and a[l] < a[l + 1])
        valley[v] = l;
      else
        seg[v] = max(a[l + 1] - a[l], a[l - 1] - a[l]);
      if (a[l - 1] <= a[l] and a[l] >= a[l + 1]) peak[v] = l;
      return;
    }
    long long mid = (l + r) / 2;
    build(2 * v, l, mid);
    build(2 * v + 1, mid, r);
    seg[v] = min(seg[2 * v], seg[2 * v + 1]);
    peak[v] = max(peak[2 * v], peak[2 * v + 1]);
    valley[v] = min(valley[2 * v], valley[2 * v + 1]);
  }
  void update(long long pos, long long x, long long st, long long v = 1,
              long long l = 1, long long r = n + 1) {
    if (r - l == 1) {
      if (st == 1) peak[v] = x;
      if (st == 2) valley[v] = x;
      if (st == 3) seg[v] = x;
      return;
    }
    long long mid = (l + r) / 2;
    if (pos < mid)
      update(pos, x, st, 2 * v, l, mid);
    else
      update(pos, x, st, 2 * v + 1, mid, r);
    seg[v] = min(seg[2 * v], seg[2 * v + 1]);
    peak[v] = max(peak[2 * v], peak[2 * v + 1]);
    valley[v] = min(valley[2 * v], valley[2 * v + 1]);
  }
  long long pek(long long L, long long R, long long v = 1, long long l = 1,
                long long r = n + 1) {
    if (r <= L or R <= l) return (0);
    if (L <= l and r <= R) return (peak[v]);
    long long mid = (l + r) / 2;
    return (max(pek(L, R, 2 * v, l, mid), pek(L, R, 2 * v + 1, mid, r)));
  }
  long long query(long long L, long long R, long long v = 1, long long l = 1,
                  long long r = n + 1) {
    if (r <= L or R <= l) return (seg[n * 4 + 1]);
    if (L <= l and r <= R) return (seg[v]);
    long long mid = (l + r) / 2;
    return (min(query(L, R, 2 * v, l, mid), query(L, R, 2 * v + 1, mid, r)));
  }
  long long valy(long long L, long long R, long long v = 1, long long l = 1,
                 long long r = n + 1) {
    if (r <= L or R <= l) return (seg[n * 4 + 1]);
    if (L <= l and r <= R) return (valley[v]);
    long long mid = (l + r) / 2;
    return (min(valy(L, R, 2 * v, l, mid), valy(L, R, 2 * v + 1, mid, r)));
  }
  long long solve(long long l, long long r, long long x) {
    if (pek(l, r)) return (2 * x);
    long long ans = -seg[n * 4 + 1];
    long long res = query(l, r);
    if (res < seg[n * 4 + 1]) ans = max(0LL, (x - res) * 2);
    res = valy(l, r);
    if (res < seg[n * 4 + 1])
      ans = max(ans, ((x < diff[res]) ? -x : x - diff[res] * 2) +
                         ((x < diff[res - 1]) ? -x : x - diff[res - 1] * 2));
    if (l == 1) ans = max(ans, abs(fen.get(1) + x - fen.get(2)) - diff[1]);
    if (r == n + 1)
      ans = max(ans, abs(fen.get(n) + x - fen.get(n - 1)) - diff[n - 1]);
    return (ans);
  }
};
segment seg(63);
void calc(long long pos) {
  if (pos < n) {
    long long b = fen.get(pos);
    long long c = fen.get(pos + 1);
    if (pos > 1) {
      long long a = fen.get(pos - 1);
      if (a <= b and b >= c) {
        seg.update(pos, pos, 1);
      } else {
        seg.update(pos, 0, 1);
      }
      if (a > b and b < c) {
        seg.update(pos, pos, 2);
        seg.update(pos, seg.seg[n * 4 + 1], 3);
      } else {
        seg.update(pos, seg.seg[n * 4 + 1], 2);
        seg.update(pos, max(c - b, a - b), 3);
      }
    }
    ans += abs(b - c) - diff[pos];
    diff[pos] = abs(b - c);
  }
}
void update(long long l, long long r, long long x) {
  fen.add(x, l, r);
  calc(l);
  if (l > 1) calc(l - 1);
  if (r != l) calc(r);
  if (r < n) calc(r + 1);
}
int32_t main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n;
  for (long long i = 1; i <= n; i++) cin >> a[i], fen.add(a[i], i, i);
  for (long long i = 1; i < n; i++)
    diff[i] = abs(a[i] - a[i + 1]), ans += diff[i];
  seg.build();
  cin >> q;
  while (q--) {
    long long t, l, r, x;
    cin >> t >> l >> r >> x;
    if (t == 1)
      cout << ans + seg.solve(l, r + 1, x) << '\n';
    else
      update(l, r, x);
  }
  return (0);
}

```