#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
template <class T>
T gcd(T a, T b) {
  if (!b) return a;
  return gcd(b, a % b);
}
const int maxn = 1e5 + 10;
int n, q;
long long a[maxn], d[maxn], f;
inline long long ABS(long long x) { return x > 0 ? x : -x; }
inline long long h(int x) { return ABS(d[x]) + ABS(d[x + 1]); }
struct pnt {
  long long e, f, g;
  pnt(long long ee = -INF, long long ff = -INF, long long gg = -INF) {
    e = ee;
    f = ff;
    g = gg;
  }
} mx[maxn << 2];
inline pnt MAX(pnt a, pnt b) {
  return pnt(max(a.e, b.e), max(a.f, b.f), max(a.g, b.g));
}
inline void pick_up(int rt) {
  mx[rt] = MAX(mx[((rt) << 1 | 1)], mx[(((rt) << 1) + 2)]);
}
void build(int rt, int l, int r) {
  if (l == r) {
    mx[rt] = pnt(d[l + 1] - d[l] - h(l), d[l] - d[l + 1] - h(l),
                 ABS(d[l] + d[l + 1]) - h(l));
    return;
  }
  build(((rt) << 1 | 1), l, ((l + r) >> 1));
  build((((rt) << 1) + 2), ((l + r) >> 1) + 1, r);
  pick_up(rt);
}
void init() { build(0, 0, n - 3); }
pnt query(int x, int y, int rt, int l, int r) {
  if (l > y || r < x) return pnt();
  if (l >= x && r <= y) return mx[rt];
  return MAX(query(x, y, ((rt) << 1 | 1), l, ((l + r) >> 1)),
             query(x, y, (((rt) << 1) + 2), ((l + r) >> 1) + 1, r));
}
void change(int x, int rt, int l, int r) {
  if (l > x || r < x) return;
  if (l == x && r == x) {
    mx[rt] = pnt(d[l + 1] - d[l] - h(l), d[l] - d[l + 1] - h(l),
                 ABS(d[l] + d[l + 1]) - h(l));
    return;
  }
  change(x, ((rt) << 1 | 1), l, ((l + r) >> 1));
  change(x, (((rt) << 1) + 2), ((l + r) >> 1) + 1, r);
  pick_up(rt);
}
int main() {
  scanf("%d", &n);
  f = 0;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n - 1; i++) d[i] = a[i + 1] - a[i];
  for (int i = 0; i < n - 1; i++) f += ABS(d[i]);
  init();
  scanf("%d", &q);
  while (q--) {
    int op, l, r, x;
    scanf("%d", &op);
    scanf("%d", &l);
    scanf("%d", &r);
    scanf("%d", &x);
    l--;
    r--;
    long long ans = -INF;
    if (op == 1) {
      l--;
      r--;
      pnt p = query(l, r, 0, 0, n - 3);
      cout << max({p.e - 2 * x, p.f + 2 * x, p.g}) + f << endl;
    } else {
      f -= ABS(d[l - 1]);
      d[l - 1] += x;
      f += ABS(d[l - 1]);
      change(l - 1, 0, 0, n - 3);
      if (l - 1) change(l - 2, 0, 0, n - 3);
      f -= ABS(d[r]);
      d[r] -= x;
      f += ABS(d[r]);
      if (r < n - 2) change(r, 0, 0, n - 3);
      change(r - 1, 0, 0, n - 3);
    }
  }
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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 mod = 1e9 + 7;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
template <class T>
T gcd(T a, T b) {
  if (!b) return a;
  return gcd(b, a % b);
}
const int maxn = 1e5 + 10;
int n, q;
long long a[maxn], d[maxn], f;
inline long long ABS(long long x) { return x > 0 ? x : -x; }
inline long long h(int x) { return ABS(d[x]) + ABS(d[x + 1]); }
struct pnt {
  long long e, f, g;
  pnt(long long ee = -INF, long long ff = -INF, long long gg = -INF) {
    e = ee;
    f = ff;
    g = gg;
  }
} mx[maxn << 2];
inline pnt MAX(pnt a, pnt b) {
  return pnt(max(a.e, b.e), max(a.f, b.f), max(a.g, b.g));
}
inline void pick_up(int rt) {
  mx[rt] = MAX(mx[((rt) << 1 | 1)], mx[(((rt) << 1) + 2)]);
}
void build(int rt, int l, int r) {
  if (l == r) {
    mx[rt] = pnt(d[l + 1] - d[l] - h(l), d[l] - d[l + 1] - h(l),
                 ABS(d[l] + d[l + 1]) - h(l));
    return;
  }
  build(((rt) << 1 | 1), l, ((l + r) >> 1));
  build((((rt) << 1) + 2), ((l + r) >> 1) + 1, r);
  pick_up(rt);
}
void init() { build(0, 0, n - 3); }
pnt query(int x, int y, int rt, int l, int r) {
  if (l > y || r < x) return pnt();
  if (l >= x && r <= y) return mx[rt];
  return MAX(query(x, y, ((rt) << 1 | 1), l, ((l + r) >> 1)),
             query(x, y, (((rt) << 1) + 2), ((l + r) >> 1) + 1, r));
}
void change(int x, int rt, int l, int r) {
  if (l > x || r < x) return;
  if (l == x && r == x) {
    mx[rt] = pnt(d[l + 1] - d[l] - h(l), d[l] - d[l + 1] - h(l),
                 ABS(d[l] + d[l + 1]) - h(l));
    return;
  }
  change(x, ((rt) << 1 | 1), l, ((l + r) >> 1));
  change(x, (((rt) << 1) + 2), ((l + r) >> 1) + 1, r);
  pick_up(rt);
}
int main() {
  scanf("%d", &n);
  f = 0;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n - 1; i++) d[i] = a[i + 1] - a[i];
  for (int i = 0; i < n - 1; i++) f += ABS(d[i]);
  init();
  scanf("%d", &q);
  while (q--) {
    int op, l, r, x;
    scanf("%d", &op);
    scanf("%d", &l);
    scanf("%d", &r);
    scanf("%d", &x);
    l--;
    r--;
    long long ans = -INF;
    if (op == 1) {
      l--;
      r--;
      pnt p = query(l, r, 0, 0, n - 3);
      cout << max({p.e - 2 * x, p.f + 2 * x, p.g}) + f << endl;
    } else {
      f -= ABS(d[l - 1]);
      d[l - 1] += x;
      f += ABS(d[l - 1]);
      change(l - 1, 0, 0, n - 3);
      if (l - 1) change(l - 2, 0, 0, n - 3);
      f -= ABS(d[r]);
      d[r] -= x;
      f += ABS(d[r]);
      if (r < n - 2) change(r, 0, 0, n - 3);
      change(r - 1, 0, 0, n - 3);
    }
  }
  return 0;
}

```