#include <bits/stdc++.h>
using namespace std;
void qmin(int &x, int y) {
  if (x > y) x = y;
}
inline int read() {
  char s;
  int k = 0, base = 1;
  while ((s = getchar()) != '-' && s != EOF && !(isdigit(s)))
    ;
  if (s == '-') base = -1, s = getchar();
  while (isdigit(s)) {
    k = k * 10 + (s ^ '0');
    s = getchar();
  }
  return k * base;
}
inline void write(int x) {
  static char cnt, num[15];
  cnt = 0;
  if (!x) {
    putchar('0');
    return;
  }
  for (; x; x /= 10) num[++cnt] = x % 10;
  for (; cnt; putchar(num[cnt--] + 48))
    ;
}
const int maxn = 1e5 + 100;
int n, a[maxn], Q, T, L, R, X;
long long b[maxn];
long long t[maxn << 2], sum, f2;
long long Abs(long long x) { return x >= 0 ? x : -x; }
void bt(int l, int r, int d) {
  if (l == r) {
    t[d] = max(0ll, -b[l]) + max(0ll, b[l + 1]);
    return;
  }
  int mid = (l + r) >> 1;
  bt(l, mid, d << 1);
  bt(mid + 1, r, d << 1 | 1);
  t[d] = min(t[d << 1], t[d << 1 | 1]);
}
long long qmax(int l, int r, int d, int x, int y) {
  if (x <= l && r <= y) {
    return t[d];
  }
  int mid = (l + r) >> 1;
  if (y <= mid)
    return qmax(l, mid, d << 1, x, y);
  else if (x > mid)
    return qmax(mid + 1, r, d << 1 | 1, x, y);
  else
    return min(qmax(l, mid, d << 1, x, mid),
               qmax(mid + 1, r, d << 1 | 1, mid + 1, y));
}
void xg(int l, int r, int d, int p) {
  if (p < 1 || p > n) return;
  if (p == l && l == r) {
    t[d] = max(0ll, -b[l]) + max(0ll, b[l + 1]);
    return;
  }
  int mid = (l + r) >> 1;
  if (p <= mid)
    xg(l, mid, d << 1, p);
  else
    xg(mid + 1, r, d << 1 | 1, p);
  t[d] = min(t[d << 1], t[d << 1 | 1]);
}
long long calc(int x, int y, int z) {
  if (x == y) {
    if (x == 1)
      if (b[2] > z)
        return -z;
      else if (b[2] > 0)
        return z - 2 * b[2];
      else
        return z;
    if (x == n)
      if (b[n] < -z)
        return -z;
      else if (b[n] < 0)
        return z + 2 * b[n];
      else
        return z;
    return -Abs(b[x]) - Abs(b[x + 1]) + Abs(b[x] + z) + Abs(b[x + 1] - z);
  }
  long long s = 0;
  if (x == 1) {
    x++;
    if (b[2] > z)
      s = -z;
    else if (b[2] > 0)
      s = z - 2 * b[2];
    else
      s = z;
  }
  if (y == n) {
    y--;
    if (b[n] < -z)
      s = max(s, 1ll * (-z));
    else if (b[n] < 0)
      s = max(s, (long long)z + 2 * b[n]);
    else
      s = max(s, (long long)z);
  }
  return max(s, 2 * z - 2 * qmax(1, n, 1, x, y));
}
signed main() {
  n = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  a[0] = a[1];
  for (int i = 1; i <= n; i++) b[i] = a[i] - a[i - 1], sum += Abs(b[i]);
  b[1] = a[1];
  b[n + 1] = 0;
  bt(1, n, 1);
  Q = read();
  long long ans;
  while (Q--) {
    T = read();
    L = read();
    R = read();
    X = read();
    if (T == 1) {
      ans = sum + calc(L, R, X);
      printf("%lld\n", ans);
    } else {
      R++;
      if (L > 1) sum -= Abs(b[L]);
      if (R > 1 && R <= n) sum -= Abs(b[R]);
      b[L] += X;
      b[R] -= X;
      if (L > 1) sum += Abs(b[L]);
      if (R > 1 && R <= n) sum += Abs(b[R]);
      xg(1, n, 1, L - 1);
      xg(1, n, 1, L);
      xg(1, n, 1, L + 1);
      xg(1, n, 1, R - 1);
      xg(1, n, 1, R);
      xg(1, n, 1, R + 1);
    }
  }
  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;
void qmin(int &x, int y) {
  if (x > y) x = y;
}
inline int read() {
  char s;
  int k = 0, base = 1;
  while ((s = getchar()) != '-' && s != EOF && !(isdigit(s)))
    ;
  if (s == '-') base = -1, s = getchar();
  while (isdigit(s)) {
    k = k * 10 + (s ^ '0');
    s = getchar();
  }
  return k * base;
}
inline void write(int x) {
  static char cnt, num[15];
  cnt = 0;
  if (!x) {
    putchar('0');
    return;
  }
  for (; x; x /= 10) num[++cnt] = x % 10;
  for (; cnt; putchar(num[cnt--] + 48))
    ;
}
const int maxn = 1e5 + 100;
int n, a[maxn], Q, T, L, R, X;
long long b[maxn];
long long t[maxn << 2], sum, f2;
long long Abs(long long x) { return x >= 0 ? x : -x; }
void bt(int l, int r, int d) {
  if (l == r) {
    t[d] = max(0ll, -b[l]) + max(0ll, b[l + 1]);
    return;
  }
  int mid = (l + r) >> 1;
  bt(l, mid, d << 1);
  bt(mid + 1, r, d << 1 | 1);
  t[d] = min(t[d << 1], t[d << 1 | 1]);
}
long long qmax(int l, int r, int d, int x, int y) {
  if (x <= l && r <= y) {
    return t[d];
  }
  int mid = (l + r) >> 1;
  if (y <= mid)
    return qmax(l, mid, d << 1, x, y);
  else if (x > mid)
    return qmax(mid + 1, r, d << 1 | 1, x, y);
  else
    return min(qmax(l, mid, d << 1, x, mid),
               qmax(mid + 1, r, d << 1 | 1, mid + 1, y));
}
void xg(int l, int r, int d, int p) {
  if (p < 1 || p > n) return;
  if (p == l && l == r) {
    t[d] = max(0ll, -b[l]) + max(0ll, b[l + 1]);
    return;
  }
  int mid = (l + r) >> 1;
  if (p <= mid)
    xg(l, mid, d << 1, p);
  else
    xg(mid + 1, r, d << 1 | 1, p);
  t[d] = min(t[d << 1], t[d << 1 | 1]);
}
long long calc(int x, int y, int z) {
  if (x == y) {
    if (x == 1)
      if (b[2] > z)
        return -z;
      else if (b[2] > 0)
        return z - 2 * b[2];
      else
        return z;
    if (x == n)
      if (b[n] < -z)
        return -z;
      else if (b[n] < 0)
        return z + 2 * b[n];
      else
        return z;
    return -Abs(b[x]) - Abs(b[x + 1]) + Abs(b[x] + z) + Abs(b[x + 1] - z);
  }
  long long s = 0;
  if (x == 1) {
    x++;
    if (b[2] > z)
      s = -z;
    else if (b[2] > 0)
      s = z - 2 * b[2];
    else
      s = z;
  }
  if (y == n) {
    y--;
    if (b[n] < -z)
      s = max(s, 1ll * (-z));
    else if (b[n] < 0)
      s = max(s, (long long)z + 2 * b[n]);
    else
      s = max(s, (long long)z);
  }
  return max(s, 2 * z - 2 * qmax(1, n, 1, x, y));
}
signed main() {
  n = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  a[0] = a[1];
  for (int i = 1; i <= n; i++) b[i] = a[i] - a[i - 1], sum += Abs(b[i]);
  b[1] = a[1];
  b[n + 1] = 0;
  bt(1, n, 1);
  Q = read();
  long long ans;
  while (Q--) {
    T = read();
    L = read();
    R = read();
    X = read();
    if (T == 1) {
      ans = sum + calc(L, R, X);
      printf("%lld\n", ans);
    } else {
      R++;
      if (L > 1) sum -= Abs(b[L]);
      if (R > 1 && R <= n) sum -= Abs(b[R]);
      b[L] += X;
      b[R] -= X;
      if (L > 1) sum += Abs(b[L]);
      if (R > 1 && R <= n) sum += Abs(b[R]);
      xg(1, n, 1, L - 1);
      xg(1, n, 1, L);
      xg(1, n, 1, L + 1);
      xg(1, n, 1, R - 1);
      xg(1, n, 1, R);
      xg(1, n, 1, R + 1);
    }
  }
  return 0;
}

```