#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 262222;
const long long INF = 1e16;
int n;
long long t1[M], t3[M], t4[M], a, b, c, d, ans, Out;
char ch;
int read() {
  int x = 0, sig = 1;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') sig = -1;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48;
  return x * sig;
}
void Add(int l, int r, int a, int b, int v, int x) {
  if (l == a && r == b) {
    t1[x] += v;
    return;
  }
  int mid = l + r >> 1;
  if (b <= mid)
    Add(l, mid, a, b, v, x << 1);
  else if (a > mid)
    Add(mid + 1, r, a, b, v, x << 1 | 1);
  else {
    Add(l, mid, a, mid, v, x << 1);
    Add(mid + 1, r, mid + 1, b, v, x << 1 | 1);
  }
}
long long getval(int g) {
  long long k = 0;
  for (int l = 1, r = n, mid, x = 1;;) {
    k += t1[x];
    if (l == r) return k;
    mid = l + r >> 1;
    if (g <= mid)
      r = mid, x <<= 1;
    else
      l = mid + 1, x = x << 1 | 1;
  }
}
void Change(int l, int r, int g, long long v, int x, long long *t) {
  if (l == r) {
    t[x] = v;
    return;
  }
  int mid = l + r >> 1;
  if (g <= mid)
    Change(l, mid, g, v, x << 1, t);
  else
    Change(mid + 1, r, g, v, x << 1 | 1, t);
  t[x] = max(t[x << 1], t[x << 1 | 1]);
}
long long getmax(int l, int r, int a, int b, int x, long long *t) {
  if (l == a && r == b) return t[x];
  int mid = l + r >> 1;
  if (b <= mid) return getmax(l, mid, a, b, x << 1, t);
  if (a > mid) return getmax(mid + 1, r, a, b, x << 1 | 1, t);
  return max(getmax(l, mid, a, mid, x << 1, t),
             getmax(mid + 1, r, mid + 1, b, x << 1 | 1, t));
}
int main() {
  for (int i = 0; i < M; i++) t3[i] = t4[i] = -INF;
  n = read();
  for (int i = 1, x; i <= n; i++) {
    x = read();
    Add(1, n, i, i, x, 1);
  }
  b = getval(1);
  c = getval(2);
  ans += abs(c - b);
  for (int i = 2; i < n; i++) {
    a = b;
    b = c;
    c = getval(i + 1);
    ans += abs(c - b);
    d = abs(a - b) + abs(c - b);
    Change(1, n, i, abs(a - c) - d, 1, t3);
    Change(1, n, i, abs(a - c) - d - 2 * (max(a, c) - b), 1, t4);
  }
  for (int q = read(), typ, l, r, x; q--;) {
    typ = read();
    l = read();
    r = read();
    x = read();
    if (typ == 1) {
      Out = -INF;
      if (l == 1) {
        a = getval(1);
        b = getval(2);
        Out = max((long long)-x, -(b - a) - abs(b - a) + x);
        l++;
      }
      if (r == n) {
        a = getval(n);
        b = getval(n - 1);
        Out = max(Out, max((long long)-x, -(b - a) - abs(b - a) + x));
        r--;
      }
      if (l <= r)
        Out = max(Out, max(max(-2ll * x, getmax(1, n, l, r, 1, t3)),
                           getmax(1, n, l, r, 1, t4) + 2 * x));
      Out += ans;
      printf("%I64d\n", Out);
    } else {
      if (l > 1) {
        a = getval(l - 1);
        b = getval(l);
        ans -= abs(a - b);
      }
      if (r < n) {
        a = getval(r);
        b = getval(r + 1);
        ans -= abs(a - b);
      }
      Add(1, n, l, r, x, 1);
      if (l > 1) {
        a = getval(l - 1);
        b = getval(l);
        c = getval(l + 1);
        ans += abs(a - b);
        d = abs(a - b) + abs(c - b);
        Change(1, n, l, abs(a - c) - d, 1, t3);
        Change(1, n, l, abs(a - c) - d - 2 * (max(a, c) - b), 1, t4);
        if (l > 2) {
          c = b;
          b = a;
          a = getval(l - 2);
          d = abs(a - b) + abs(c - b);
          Change(1, n, l - 1, abs(a - c) - d, 1, t3);
          Change(1, n, l - 1, abs(a - c) - d - 2 * (max(a, c) - b), 1, t4);
        }
      }
      if (r < n) {
        a = getval(r - 1);
        b = getval(r);
        c = getval(r + 1);
        ans += abs(b - c);
        d = abs(a - b) + abs(c - b);
        Change(1, n, r, abs(a - c) - d, 1, t3);
        Change(1, n, r, abs(a - c) - d - 2 * (max(a, c) - b), 1, t4);
        if (r < n - 1) {
          a = b;
          b = c;
          c = getval(r + 2);
          d = abs(a - b) + abs(c - b);
          Change(1, n, r + 1, abs(a - c) - d, 1, t3);
          Change(1, n, r + 1, abs(a - c) - d - 2 * (max(a, c) - b), 1, t4);
        }
      }
    }
  }
  return 0;
}

### Prompt

Generate 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;
const int N = 1e5 + 5, M = 262222;
const long long INF = 1e16;
int n;
long long t1[M], t3[M], t4[M], a, b, c, d, ans, Out;
char ch;
int read() {
  int x = 0, sig = 1;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') sig = -1;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48;
  return x * sig;
}
void Add(int l, int r, int a, int b, int v, int x) {
  if (l == a && r == b) {
    t1[x] += v;
    return;
  }
  int mid = l + r >> 1;
  if (b <= mid)
    Add(l, mid, a, b, v, x << 1);
  else if (a > mid)
    Add(mid + 1, r, a, b, v, x << 1 | 1);
  else {
    Add(l, mid, a, mid, v, x << 1);
    Add(mid + 1, r, mid + 1, b, v, x << 1 | 1);
  }
}
long long getval(int g) {
  long long k = 0;
  for (int l = 1, r = n, mid, x = 1;;) {
    k += t1[x];
    if (l == r) return k;
    mid = l + r >> 1;
    if (g <= mid)
      r = mid, x <<= 1;
    else
      l = mid + 1, x = x << 1 | 1;
  }
}
void Change(int l, int r, int g, long long v, int x, long long *t) {
  if (l == r) {
    t[x] = v;
    return;
  }
  int mid = l + r >> 1;
  if (g <= mid)
    Change(l, mid, g, v, x << 1, t);
  else
    Change(mid + 1, r, g, v, x << 1 | 1, t);
  t[x] = max(t[x << 1], t[x << 1 | 1]);
}
long long getmax(int l, int r, int a, int b, int x, long long *t) {
  if (l == a && r == b) return t[x];
  int mid = l + r >> 1;
  if (b <= mid) return getmax(l, mid, a, b, x << 1, t);
  if (a > mid) return getmax(mid + 1, r, a, b, x << 1 | 1, t);
  return max(getmax(l, mid, a, mid, x << 1, t),
             getmax(mid + 1, r, mid + 1, b, x << 1 | 1, t));
}
int main() {
  for (int i = 0; i < M; i++) t3[i] = t4[i] = -INF;
  n = read();
  for (int i = 1, x; i <= n; i++) {
    x = read();
    Add(1, n, i, i, x, 1);
  }
  b = getval(1);
  c = getval(2);
  ans += abs(c - b);
  for (int i = 2; i < n; i++) {
    a = b;
    b = c;
    c = getval(i + 1);
    ans += abs(c - b);
    d = abs(a - b) + abs(c - b);
    Change(1, n, i, abs(a - c) - d, 1, t3);
    Change(1, n, i, abs(a - c) - d - 2 * (max(a, c) - b), 1, t4);
  }
  for (int q = read(), typ, l, r, x; q--;) {
    typ = read();
    l = read();
    r = read();
    x = read();
    if (typ == 1) {
      Out = -INF;
      if (l == 1) {
        a = getval(1);
        b = getval(2);
        Out = max((long long)-x, -(b - a) - abs(b - a) + x);
        l++;
      }
      if (r == n) {
        a = getval(n);
        b = getval(n - 1);
        Out = max(Out, max((long long)-x, -(b - a) - abs(b - a) + x));
        r--;
      }
      if (l <= r)
        Out = max(Out, max(max(-2ll * x, getmax(1, n, l, r, 1, t3)),
                           getmax(1, n, l, r, 1, t4) + 2 * x));
      Out += ans;
      printf("%I64d\n", Out);
    } else {
      if (l > 1) {
        a = getval(l - 1);
        b = getval(l);
        ans -= abs(a - b);
      }
      if (r < n) {
        a = getval(r);
        b = getval(r + 1);
        ans -= abs(a - b);
      }
      Add(1, n, l, r, x, 1);
      if (l > 1) {
        a = getval(l - 1);
        b = getval(l);
        c = getval(l + 1);
        ans += abs(a - b);
        d = abs(a - b) + abs(c - b);
        Change(1, n, l, abs(a - c) - d, 1, t3);
        Change(1, n, l, abs(a - c) - d - 2 * (max(a, c) - b), 1, t4);
        if (l > 2) {
          c = b;
          b = a;
          a = getval(l - 2);
          d = abs(a - b) + abs(c - b);
          Change(1, n, l - 1, abs(a - c) - d, 1, t3);
          Change(1, n, l - 1, abs(a - c) - d - 2 * (max(a, c) - b), 1, t4);
        }
      }
      if (r < n) {
        a = getval(r - 1);
        b = getval(r);
        c = getval(r + 1);
        ans += abs(b - c);
        d = abs(a - b) + abs(c - b);
        Change(1, n, r, abs(a - c) - d, 1, t3);
        Change(1, n, r, abs(a - c) - d - 2 * (max(a, c) - b), 1, t4);
        if (r < n - 1) {
          a = b;
          b = c;
          c = getval(r + 2);
          d = abs(a - b) + abs(c - b);
          Change(1, n, r + 1, abs(a - c) - d, 1, t3);
          Change(1, n, r + 1, abs(a - c) - d - 2 * (max(a, c) - b), 1, t4);
        }
      }
    }
  }
  return 0;
}

```