#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && (c != '-')) c = getchar();
  if (c == '-') f = -1, c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
const int N = 1e5 + 10;
int n, q, a[N];
const long long inf = 1e15;
struct node {
  long long vl, vr, s, mn0, mn1;
  long long a, z;
  bool flag;
  inline node operator+(const node &p) const {
    node ret;
    ret.mn0 = min(mn0, p.mn0);
    ret.mn1 = min(mn1, p.mn1);
    if (a)
      ret.a = a, ret.z = z;
    else
      ret.a = p.a, ret.z = p.z;
    ret.vl = vl, ret.vr = p.vr;
    ret.s = s + p.s, ret.flag = flag | p.flag;
    if (vr >= 0 && p.vl <= 0) ret.flag = 1;
    if (vr <= 0 && p.vl >= 0) ret.a = vr, ret.z = p.vl;
    if (vr <= 0 && p.vl <= 0) ret.mn0 = min(ret.mn0, abs(vr));
    if (vr >= 0 && p.vl >= 0) ret.mn1 = min(ret.mn1, abs(p.vl));
    return ret;
  }
};
node v[N << 2];
inline void Build(int u, int l, int r) {
  if (l == r) {
    v[u].vl = v[u].vr = a[l] - a[l - 1], v[u].s = abs(a[l] - a[l - 1]);
    v[u].flag = 0;
    v[u].mn0 = v[u].mn1 = inf;
    v[u].a = v[u].z = 0;
    return;
  }
  int mid = l + r >> 1;
  Build(u << 1, l, mid), Build(u << 1 ^ 1, mid + 1, r);
  v[u] = v[u << 1] + v[u << 1 ^ 1];
}
inline void update(int u, int l, int r, int ql, int x) {
  if (l == r) {
    long long y = v[u].vl + x;
    v[u].vl = v[u].vr = y, v[u].s = abs(y);
    v[u].flag = 0;
    v[u].mn0 = v[u].mn1 = inf;
    v[u].a = v[u].z = 0;
    return;
  }
  int mid = l + r >> 1;
  if (ql <= mid)
    update(u << 1, l, mid, ql, x);
  else
    update(u << 1 ^ 1, mid + 1, r, ql, x);
  v[u] = v[u << 1] + v[u << 1 ^ 1];
}
inline node Query(int u, int l, int r, int ql, int qr) {
  if (l >= ql && r <= qr) return v[u];
  int mid = l + r >> 1;
  if (qr <= mid) return Query(u << 1, l, mid, ql, qr);
  if (ql > mid) return Query(u << 1 ^ 1, mid + 1, r, ql, qr);
  return Query(u << 1, l, mid, ql, qr) + Query(u << 1 ^ 1, mid + 1, r, ql, qr);
}
int main() {
  n = read();
  for (register int i = (1); i <= (n); i++) a[i] = read();
  Build(1, 2, n);
  q = read();
  int cnt = 0;
  for (register int i = (1); i <= (q); i++) {
    int opt = read(), l = read(), r = read(), x = read();
    if (opt == 2) {
      if (l > 1) update(1, 2, n, l, x);
      if (r < n) update(1, 2, n, r + 1, -x);
    }
    if (opt == 1) {
      ++cnt;
      node ret = Query(1, 2, n, max(l, 2), min(n, r + 1));
      long long ans = 0;
      if (ret.flag)
        ans = v[1].s + 2 * x;
      else {
        if (ret.mn0 != inf)
          ans = max(ans, v[1].s - ret.mn0 + x + abs(-ret.mn0 + x));
        if (ret.mn1 != inf)
          ans = max(ans, v[1].s - ret.mn1 + x + abs(ret.mn1 - x));
        if (ret.a && ret.z)
          ans = max(ans, v[1].s - abs(ret.a) - abs(ret.z) + abs(ret.a + x) +
                             abs(ret.z - x));
      }
      if (l == 1) ans = max(ans, v[1].s - ret.vl + abs(ret.vl - x));
      if (r == n) ans = max(ans, v[1].s - ret.vr + abs(ret.vr + x));
      printf("%lld\n", ans);
    }
  }
}

### 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 x = 0, f = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && (c != '-')) c = getchar();
  if (c == '-') f = -1, c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
const int N = 1e5 + 10;
int n, q, a[N];
const long long inf = 1e15;
struct node {
  long long vl, vr, s, mn0, mn1;
  long long a, z;
  bool flag;
  inline node operator+(const node &p) const {
    node ret;
    ret.mn0 = min(mn0, p.mn0);
    ret.mn1 = min(mn1, p.mn1);
    if (a)
      ret.a = a, ret.z = z;
    else
      ret.a = p.a, ret.z = p.z;
    ret.vl = vl, ret.vr = p.vr;
    ret.s = s + p.s, ret.flag = flag | p.flag;
    if (vr >= 0 && p.vl <= 0) ret.flag = 1;
    if (vr <= 0 && p.vl >= 0) ret.a = vr, ret.z = p.vl;
    if (vr <= 0 && p.vl <= 0) ret.mn0 = min(ret.mn0, abs(vr));
    if (vr >= 0 && p.vl >= 0) ret.mn1 = min(ret.mn1, abs(p.vl));
    return ret;
  }
};
node v[N << 2];
inline void Build(int u, int l, int r) {
  if (l == r) {
    v[u].vl = v[u].vr = a[l] - a[l - 1], v[u].s = abs(a[l] - a[l - 1]);
    v[u].flag = 0;
    v[u].mn0 = v[u].mn1 = inf;
    v[u].a = v[u].z = 0;
    return;
  }
  int mid = l + r >> 1;
  Build(u << 1, l, mid), Build(u << 1 ^ 1, mid + 1, r);
  v[u] = v[u << 1] + v[u << 1 ^ 1];
}
inline void update(int u, int l, int r, int ql, int x) {
  if (l == r) {
    long long y = v[u].vl + x;
    v[u].vl = v[u].vr = y, v[u].s = abs(y);
    v[u].flag = 0;
    v[u].mn0 = v[u].mn1 = inf;
    v[u].a = v[u].z = 0;
    return;
  }
  int mid = l + r >> 1;
  if (ql <= mid)
    update(u << 1, l, mid, ql, x);
  else
    update(u << 1 ^ 1, mid + 1, r, ql, x);
  v[u] = v[u << 1] + v[u << 1 ^ 1];
}
inline node Query(int u, int l, int r, int ql, int qr) {
  if (l >= ql && r <= qr) return v[u];
  int mid = l + r >> 1;
  if (qr <= mid) return Query(u << 1, l, mid, ql, qr);
  if (ql > mid) return Query(u << 1 ^ 1, mid + 1, r, ql, qr);
  return Query(u << 1, l, mid, ql, qr) + Query(u << 1 ^ 1, mid + 1, r, ql, qr);
}
int main() {
  n = read();
  for (register int i = (1); i <= (n); i++) a[i] = read();
  Build(1, 2, n);
  q = read();
  int cnt = 0;
  for (register int i = (1); i <= (q); i++) {
    int opt = read(), l = read(), r = read(), x = read();
    if (opt == 2) {
      if (l > 1) update(1, 2, n, l, x);
      if (r < n) update(1, 2, n, r + 1, -x);
    }
    if (opt == 1) {
      ++cnt;
      node ret = Query(1, 2, n, max(l, 2), min(n, r + 1));
      long long ans = 0;
      if (ret.flag)
        ans = v[1].s + 2 * x;
      else {
        if (ret.mn0 != inf)
          ans = max(ans, v[1].s - ret.mn0 + x + abs(-ret.mn0 + x));
        if (ret.mn1 != inf)
          ans = max(ans, v[1].s - ret.mn1 + x + abs(ret.mn1 - x));
        if (ret.a && ret.z)
          ans = max(ans, v[1].s - abs(ret.a) - abs(ret.z) + abs(ret.a + x) +
                             abs(ret.z - x));
      }
      if (l == 1) ans = max(ans, v[1].s - ret.vl + abs(ret.vl - x));
      if (r == n) ans = max(ans, v[1].s - ret.vr + abs(ret.vr + x));
      printf("%lld\n", ans);
    }
  }
}

```