#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long num = 0, neg = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') neg = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    num = (num << 3) + (num << 1) + c - '0';
    c = getchar();
  }
  return num * neg;
}
const long long INF = 0x7f7f7f7f7f7f7f;
long long n, a[100010], Q;
long long tree[100010 << 2], ta[100010 << 2], tb[100010 << 2], tc[100010 << 2],
    tag[100010 << 2];
inline void push_up(long long x) {
  ta[x] = (ta[x << 1] | ta[x << 1 | 1]);
  tb[x] = min(tb[x << 1], tb[x << 1 | 1]);
  tc[x] = max(tc[x << 1], tc[x << 1 | 1]);
  tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
}
inline void build(long long l, long long r, long long x) {
  if (l == r) {
    ta[x] = tc[x] = 0, tb[x] = INF;
    long long le = a[l - 1], ri = a[l + 1];
    if (le > ri) swap(le, ri);
    if (a[l] >= ri)
      ta[x] = 1;
    else {
      if (a[l] >= le)
        tb[x] = ri - a[l];
      else
        tc[x] = l;
    }
    tree[x] = a[l];
    return;
  }
  long long mid = l + r >> 1;
  build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
  push_up(x);
  return;
}
inline void push_down(long long x) {
  if (tag[x]) {
    tree[x << 1] += tag[x], tree[x << 1 | 1] += tag[x];
    tag[x << 1] += tag[x], tag[x << 1 | 1] += tag[x];
    tag[x] = 0;
  }
}
inline void update(long long ul, long long ur, long long l, long long r,
                   long long x, long long k) {
  if (ul <= l && ur >= r) {
    tree[x] += k;
    tag[x] += k;
    return;
  }
  long long mid = l + r >> 1;
  push_down(x);
  if (ul <= mid) update(ul, ur, l, mid, x << 1, k);
  if (ur > mid) update(ul, ur, mid + 1, r, x << 1 | 1, k);
  push_up(x);
  return;
}
inline long long query(long long q, long long l, long long r, long long x) {
  if (l < 1 || r > n) return 0;
  if (l == r) return tree[x];
  long long mid = l + r >> 1, res = 0;
  push_down(x);
  if (q <= mid)
    res = query(q, l, mid, x << 1);
  else
    res = query(q, mid + 1, r, x << 1 | 1);
  push_up(x);
  return res;
}
inline void fix(long long u, long long l, long long r, long long x) {
  if (u <= 1 || u >= n) return;
  if (l == r) {
    ta[x] = tc[x] = 0, tb[x] = INF;
    long long le = query(u - 1, 1, n, 1), ri = query(u + 1, 1, n, 1);
    if (le > ri) swap(le, ri);
    if (tree[x] >= ri)
      ta[x] = 1;
    else {
      if (tree[x] >= le)
        tb[x] = ri - tree[x];
      else
        tc[x] = u;
    }
    return;
  }
  long long mid = l + r >> 1;
  push_down(x);
  if (u <= mid)
    fix(u, l, mid, x << 1);
  else
    fix(u, mid + 1, r, x << 1 | 1);
  push_up(x);
}
inline long long querya(long long ql, long long qr, long long l, long long r,
                        long long x) {
  if (ql <= l && qr >= r) return ta[x];
  long long mid = l + r >> 1, res = 0;
  push_down(x);
  if (ql <= mid) res |= querya(ql, qr, l, mid, x << 1);
  if (qr > mid) res |= querya(ql, qr, mid + 1, r, x << 1 | 1);
  push_up(x);
  return res;
}
inline long long queryb(long long ql, long long qr, long long l, long long r,
                        long long x) {
  if (ql <= l && qr >= r) return tb[x];
  long long mid = l + r >> 1, res = INF;
  push_down(x);
  if (ql <= mid) res = min(res, queryb(ql, qr, l, mid, x << 1));
  if (qr > mid) res = min(res, queryb(ql, qr, mid + 1, r, x << 1 | 1));
  push_up(x);
  return res;
}
inline long long queryc(long long ql, long long qr, long long l, long long r,
                        long long x) {
  if (ql <= l && qr >= r) return tc[x];
  long long mid = l + r >> 1, res = 0;
  push_down(x);
  if (ql <= mid) res = max(res, queryc(ql, qr, l, mid, x << 1));
  if (qr > mid) res = max(res, queryc(ql, qr, mid + 1, r, x << 1 | 1));
  push_up(x);
  return res;
}
signed main() {
  n = read();
  long long res = 0;
  for (long long i = 1; i <= n; i++) a[i] = read();
  for (long long i = 2; i <= n; i++) res += abs(a[i] - a[i - 1]);
  build(1, n, 1);
  Q = read();
  while (Q--) {
    long long op = read(), l = read(), r = read(), k = read();
    if (op == 1) {
      long long ans = -INF;
      if (l == 1) {
        long long x = query(1, 1, n, 1), ri = query(2, 1, n, 1);
        if (ri <= x)
          ans = k;
        else if (k < ri - x)
          ans = -k;
        else
          ans = k - 2 * (ri - x);
        l++;
      }
      if (r == n) {
        long long x = query(n, 1, n, 1), ri = query(n - 1, 1, n, 1);
        if (ri <= x)
          ans = max(ans, k);
        else if (k < ri - x)
          ans = max(ans, -k);
        else
          ans = max(ans, k - 2 * (ri - x));
        r--;
      }
      if (l <= r) {
        if (querya(l, r, 1, n, 1))
          ans = 2 * k;
        else {
          long long c = queryc(l, r, 1, n, 1), le, x, ri;
          if (c) {
            le = query(c - 1, 1, n, 1), x = query(c, 1, n, 1),
            ri = query(c + 1, 1, n, 1);
            if (le > ri) swap(le, ri);
            ans = max(ans, 2ll * max(k - (ri - x), 0ll) - 2ll * min(le - x, k));
          }
          long long tmp = queryb(l, r, 1, n, 1);
          if (tmp != INF) ans = max(ans, 2ll * max(k - tmp, 0ll));
        }
      }
      printf("%lld\n", res + ans);
    } else {
      if (l > 1) res -= abs(query(l, 1, n, 1) - query(l - 1, 1, n, 1));
      if (r < n) res -= abs(query(r, 1, n, 1) - query(r + 1, 1, n, 1));
      update(l, r, 1, n, 1, k);
      if (l > 1) res += abs(query(l, 1, n, 1) - query(l - 1, 1, n, 1));
      if (r < n) res += abs(query(r, 1, n, 1) - query(r + 1, 1, n, 1));
      fix(l, 1, n, 1), fix(l - 1, 1, n, 1);
      fix(r, 1, n, 1), fix(r + 1, 1, n, 1);
    }
  }
  return 0;
}

### 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;
inline long long read() {
  long long num = 0, neg = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') neg = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    num = (num << 3) + (num << 1) + c - '0';
    c = getchar();
  }
  return num * neg;
}
const long long INF = 0x7f7f7f7f7f7f7f;
long long n, a[100010], Q;
long long tree[100010 << 2], ta[100010 << 2], tb[100010 << 2], tc[100010 << 2],
    tag[100010 << 2];
inline void push_up(long long x) {
  ta[x] = (ta[x << 1] | ta[x << 1 | 1]);
  tb[x] = min(tb[x << 1], tb[x << 1 | 1]);
  tc[x] = max(tc[x << 1], tc[x << 1 | 1]);
  tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
}
inline void build(long long l, long long r, long long x) {
  if (l == r) {
    ta[x] = tc[x] = 0, tb[x] = INF;
    long long le = a[l - 1], ri = a[l + 1];
    if (le > ri) swap(le, ri);
    if (a[l] >= ri)
      ta[x] = 1;
    else {
      if (a[l] >= le)
        tb[x] = ri - a[l];
      else
        tc[x] = l;
    }
    tree[x] = a[l];
    return;
  }
  long long mid = l + r >> 1;
  build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
  push_up(x);
  return;
}
inline void push_down(long long x) {
  if (tag[x]) {
    tree[x << 1] += tag[x], tree[x << 1 | 1] += tag[x];
    tag[x << 1] += tag[x], tag[x << 1 | 1] += tag[x];
    tag[x] = 0;
  }
}
inline void update(long long ul, long long ur, long long l, long long r,
                   long long x, long long k) {
  if (ul <= l && ur >= r) {
    tree[x] += k;
    tag[x] += k;
    return;
  }
  long long mid = l + r >> 1;
  push_down(x);
  if (ul <= mid) update(ul, ur, l, mid, x << 1, k);
  if (ur > mid) update(ul, ur, mid + 1, r, x << 1 | 1, k);
  push_up(x);
  return;
}
inline long long query(long long q, long long l, long long r, long long x) {
  if (l < 1 || r > n) return 0;
  if (l == r) return tree[x];
  long long mid = l + r >> 1, res = 0;
  push_down(x);
  if (q <= mid)
    res = query(q, l, mid, x << 1);
  else
    res = query(q, mid + 1, r, x << 1 | 1);
  push_up(x);
  return res;
}
inline void fix(long long u, long long l, long long r, long long x) {
  if (u <= 1 || u >= n) return;
  if (l == r) {
    ta[x] = tc[x] = 0, tb[x] = INF;
    long long le = query(u - 1, 1, n, 1), ri = query(u + 1, 1, n, 1);
    if (le > ri) swap(le, ri);
    if (tree[x] >= ri)
      ta[x] = 1;
    else {
      if (tree[x] >= le)
        tb[x] = ri - tree[x];
      else
        tc[x] = u;
    }
    return;
  }
  long long mid = l + r >> 1;
  push_down(x);
  if (u <= mid)
    fix(u, l, mid, x << 1);
  else
    fix(u, mid + 1, r, x << 1 | 1);
  push_up(x);
}
inline long long querya(long long ql, long long qr, long long l, long long r,
                        long long x) {
  if (ql <= l && qr >= r) return ta[x];
  long long mid = l + r >> 1, res = 0;
  push_down(x);
  if (ql <= mid) res |= querya(ql, qr, l, mid, x << 1);
  if (qr > mid) res |= querya(ql, qr, mid + 1, r, x << 1 | 1);
  push_up(x);
  return res;
}
inline long long queryb(long long ql, long long qr, long long l, long long r,
                        long long x) {
  if (ql <= l && qr >= r) return tb[x];
  long long mid = l + r >> 1, res = INF;
  push_down(x);
  if (ql <= mid) res = min(res, queryb(ql, qr, l, mid, x << 1));
  if (qr > mid) res = min(res, queryb(ql, qr, mid + 1, r, x << 1 | 1));
  push_up(x);
  return res;
}
inline long long queryc(long long ql, long long qr, long long l, long long r,
                        long long x) {
  if (ql <= l && qr >= r) return tc[x];
  long long mid = l + r >> 1, res = 0;
  push_down(x);
  if (ql <= mid) res = max(res, queryc(ql, qr, l, mid, x << 1));
  if (qr > mid) res = max(res, queryc(ql, qr, mid + 1, r, x << 1 | 1));
  push_up(x);
  return res;
}
signed main() {
  n = read();
  long long res = 0;
  for (long long i = 1; i <= n; i++) a[i] = read();
  for (long long i = 2; i <= n; i++) res += abs(a[i] - a[i - 1]);
  build(1, n, 1);
  Q = read();
  while (Q--) {
    long long op = read(), l = read(), r = read(), k = read();
    if (op == 1) {
      long long ans = -INF;
      if (l == 1) {
        long long x = query(1, 1, n, 1), ri = query(2, 1, n, 1);
        if (ri <= x)
          ans = k;
        else if (k < ri - x)
          ans = -k;
        else
          ans = k - 2 * (ri - x);
        l++;
      }
      if (r == n) {
        long long x = query(n, 1, n, 1), ri = query(n - 1, 1, n, 1);
        if (ri <= x)
          ans = max(ans, k);
        else if (k < ri - x)
          ans = max(ans, -k);
        else
          ans = max(ans, k - 2 * (ri - x));
        r--;
      }
      if (l <= r) {
        if (querya(l, r, 1, n, 1))
          ans = 2 * k;
        else {
          long long c = queryc(l, r, 1, n, 1), le, x, ri;
          if (c) {
            le = query(c - 1, 1, n, 1), x = query(c, 1, n, 1),
            ri = query(c + 1, 1, n, 1);
            if (le > ri) swap(le, ri);
            ans = max(ans, 2ll * max(k - (ri - x), 0ll) - 2ll * min(le - x, k));
          }
          long long tmp = queryb(l, r, 1, n, 1);
          if (tmp != INF) ans = max(ans, 2ll * max(k - tmp, 0ll));
        }
      }
      printf("%lld\n", res + ans);
    } else {
      if (l > 1) res -= abs(query(l, 1, n, 1) - query(l - 1, 1, n, 1));
      if (r < n) res -= abs(query(r, 1, n, 1) - query(r + 1, 1, n, 1));
      update(l, r, 1, n, 1, k);
      if (l > 1) res += abs(query(l, 1, n, 1) - query(l - 1, 1, n, 1));
      if (r < n) res += abs(query(r, 1, n, 1) - query(r + 1, 1, n, 1));
      fix(l, 1, n, 1), fix(l - 1, 1, n, 1);
      fix(r, 1, n, 1), fix(r + 1, 1, n, 1);
    }
  }
  return 0;
}

```