#include <bits/stdc++.h>
using namespace std;
const long long mxn = 1e5 + 5;
const long long mod = 1e9 + 7;
long long gcd(long long a, long long b) { return !b ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return (a / gcd(a, b)) * b; }
long long pw(long long x, long long y) {
  long long r = 1;
  while (y) {
    if (y & 1) r = 1LL * r * x % mod;
    x = 1LL * x * x % mod;
    y >>= 1;
  }
  return r;
}
long long ans = 0;
long long p[mxn << 2], a[mxn];
void build(long long v, long long tl, long long tr) {
  if (tl == tr) {
    if (tl > 1) p[v] = max(-a[tl - 1], 0ll) + max(a[tl], 0ll);
    return;
  } else {
    long long tm = (tl + tr) >> 1;
    build((v << 1), tl, tm);
    build(((v << 1) | 1), tm + 1, tr);
    p[v] = min(p[(v << 1)], p[((v << 1) | 1)]);
  }
}
void add(long long v, long long tl, long long tr, long long pos,
         long long val) {
  if (tl == tr) {
    ans += abs(a[tl] + val) - abs(a[tl]);
    a[tl] += val;
    if (tl > 1) p[v] = max(-a[tl - 1], 0ll) + max(a[tl], 0ll);
    return;
  } else {
    long long tm = (tl + tr) >> 1;
    if (pos <= tm)
      add((v << 1), tl, tm, pos, val);
    else
      add(((v << 1) | 1), tm + 1, tr, pos, val);
    p[v] = min(p[(v << 1)], p[((v << 1) | 1)]);
  }
}
long long ask(long long v, long long tl, long long tr, long long l,
              long long r) {
  if (l <= tl && r >= tr) return p[v];
  long long tm = (tl + tr) >> 1;
  if (r <= tm) return ask((v << 1), tl, tm, l, r);
  if (l >= tm + 1) return ask(((v << 1) | 1), tm + 1, tr, l, r);
  return min(ask((v << 1), tl, tm, l, r),
             ask(((v << 1) | 1), tm + 1, tr, l, r));
}
signed main() {
  long long n;
  cin >> n;
  for (long long i = 1; i <= n; i++) cin >> a[i];
  for (long long i = 1; i < n; i++) a[i] = a[i + 1] - a[i], ans += abs(a[i]);
  build(1, 1, n - 1);
  long long q;
  cin >> q;
  while (q--) {
    long long tp, l, r, x;
    cin >> tp >> l >> r >> x;
    if (tp == 2) {
      if (l >= 2) add(1, 1, n - 1, l - 1, x), add(1, 1, n - 1, l, 0);
      if (r < n) add(1, 1, n - 1, r, -x), add(1, 1, n - 1, r + 1, 0);
    } else {
      if (l == r) {
        if (l == 1) {
          cout << ans - abs(a[l]) + abs(a[l] - x) << '\n';
          ;
        } else if (r == n) {
          cout << ans - abs(a[r - 1]) + abs(a[r - 1] + x) << '\n';
          ;
        } else {
          cout << ans - abs(a[l]) + abs(a[l] - x) - abs(a[l - 1]) +
                      abs(a[l - 1] + x)
               << '\n';
          ;
        }
      } else {
        long long tmp = 2ll * (x - ask(1, 1, n - 1, l > 1 ? l : 2, r));
        if (l == 1) tmp = max(tmp, -abs(a[l]) + abs(a[l] - x));
        if (r == n) tmp = max(tmp, -abs(a[r - 1]) + abs(a[r - 1] + x));
        cout << ans + max(tmp, 0ll) << '\n';
        ;
      }
    }
  }
  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;
const long long mxn = 1e5 + 5;
const long long mod = 1e9 + 7;
long long gcd(long long a, long long b) { return !b ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return (a / gcd(a, b)) * b; }
long long pw(long long x, long long y) {
  long long r = 1;
  while (y) {
    if (y & 1) r = 1LL * r * x % mod;
    x = 1LL * x * x % mod;
    y >>= 1;
  }
  return r;
}
long long ans = 0;
long long p[mxn << 2], a[mxn];
void build(long long v, long long tl, long long tr) {
  if (tl == tr) {
    if (tl > 1) p[v] = max(-a[tl - 1], 0ll) + max(a[tl], 0ll);
    return;
  } else {
    long long tm = (tl + tr) >> 1;
    build((v << 1), tl, tm);
    build(((v << 1) | 1), tm + 1, tr);
    p[v] = min(p[(v << 1)], p[((v << 1) | 1)]);
  }
}
void add(long long v, long long tl, long long tr, long long pos,
         long long val) {
  if (tl == tr) {
    ans += abs(a[tl] + val) - abs(a[tl]);
    a[tl] += val;
    if (tl > 1) p[v] = max(-a[tl - 1], 0ll) + max(a[tl], 0ll);
    return;
  } else {
    long long tm = (tl + tr) >> 1;
    if (pos <= tm)
      add((v << 1), tl, tm, pos, val);
    else
      add(((v << 1) | 1), tm + 1, tr, pos, val);
    p[v] = min(p[(v << 1)], p[((v << 1) | 1)]);
  }
}
long long ask(long long v, long long tl, long long tr, long long l,
              long long r) {
  if (l <= tl && r >= tr) return p[v];
  long long tm = (tl + tr) >> 1;
  if (r <= tm) return ask((v << 1), tl, tm, l, r);
  if (l >= tm + 1) return ask(((v << 1) | 1), tm + 1, tr, l, r);
  return min(ask((v << 1), tl, tm, l, r),
             ask(((v << 1) | 1), tm + 1, tr, l, r));
}
signed main() {
  long long n;
  cin >> n;
  for (long long i = 1; i <= n; i++) cin >> a[i];
  for (long long i = 1; i < n; i++) a[i] = a[i + 1] - a[i], ans += abs(a[i]);
  build(1, 1, n - 1);
  long long q;
  cin >> q;
  while (q--) {
    long long tp, l, r, x;
    cin >> tp >> l >> r >> x;
    if (tp == 2) {
      if (l >= 2) add(1, 1, n - 1, l - 1, x), add(1, 1, n - 1, l, 0);
      if (r < n) add(1, 1, n - 1, r, -x), add(1, 1, n - 1, r + 1, 0);
    } else {
      if (l == r) {
        if (l == 1) {
          cout << ans - abs(a[l]) + abs(a[l] - x) << '\n';
          ;
        } else if (r == n) {
          cout << ans - abs(a[r - 1]) + abs(a[r - 1] + x) << '\n';
          ;
        } else {
          cout << ans - abs(a[l]) + abs(a[l] - x) - abs(a[l - 1]) +
                      abs(a[l - 1] + x)
               << '\n';
          ;
        }
      } else {
        long long tmp = 2ll * (x - ask(1, 1, n - 1, l > 1 ? l : 2, r));
        if (l == 1) tmp = max(tmp, -abs(a[l]) + abs(a[l] - x));
        if (r == n) tmp = max(tmp, -abs(a[r - 1]) + abs(a[r - 1] + x));
        cout << ans + max(tmp, 0ll) << '\n';
        ;
      }
    }
  }
  return 0;
}

```