#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3fll;
const long long M = 1e9 + 7;
const long long maxn = 1e5 + 7;
const double eps = 0.00000001;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline T powMM(T a, T b) {
  T ret = 1;
  for (; b; b >>= 1ll, a = 1ll * a * a % M)
    if (b & 1) ret = 1ll * ret * a % M;
  return ret;
}
struct node {
  long long del, sum, add;
} T[maxn << 2];
long long a[maxn];
node merge(const node &A, const node &B) {
  node ret;
  ret.del = max(A.del, B.del);
  ret.sum = max(A.sum, B.sum);
  ret.add = max(A.add, B.add);
  return ret;
}
void update(int x, int pos, int L, int R) {
  if (L == R) {
    T[x].del = a[L + 1] - a[L] - abs(a[L]) - abs(a[L + 1]);
    T[x].add = a[L] - a[L + 1] - abs(a[L]) - abs(a[L + 1]);
    T[x].sum = abs(a[L] + a[L + 1]) - abs(a[L]) - abs(a[L + 1]);
    return;
  }
  int mid = (L + R) / 2;
  if (pos <= mid)
    update(x << 1, pos, L, mid);
  else
    update(x << 1 | 1, pos, mid + 1, R);
  T[x] = merge(T[x << 1], T[x << 1 | 1]);
}
node query(int x, int l, int r, int L, int R) {
  if (l <= L && R <= r) return T[x];
  int mid = (L + R) / 2;
  if (r <= mid)
    return query(x << 1, l, r, L, mid);
  else if (mid < l)
    return query(x << 1 | 1, l, r, mid + 1, R);
  else
    return merge(query(x << 1, l, r, L, mid),
                 query(x << 1 | 1, l, r, mid + 1, R));
}
int n, m, q;
int i, j;
long long all;
int main() {
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%I64d", &a[i]);
  for (i = n; i >= 2; i--) a[i] -= a[i - 1];
  a[1] = 0;
  for (i = 2; i <= n; i++) update(1, i, 1, n), all += abs(a[i]);
  scanf("%d", &q);
  while (q--) {
    int op, l, r, x;
    scanf("%d%d%d%d", &op, &l, &r, &x);
    if (op == 1) {
      long long ans = -INFF;
      if (l == 1) ans = max(ans, abs(a[2] - x) - abs(a[2])), l++;
      if (r == n) ans = max(ans, abs(a[n] + x) - abs(a[n])), r--;
      if (l <= r) {
        node now = query(1, l, r, 1, n);
        ans = max(ans, now.sum);
        ans = max(ans, now.del - 2 * x);
        ans = max(ans, now.add + 2 * x);
      }
      printf("%I64d\n", ans + all);
    } else {
      if (2 <= l) {
        all -= abs(a[l]);
        a[l] += x;
        all += abs(a[l]);
        update(1, l, 1, n);
        update(1, l - 1, 1, n);
      }
      if (r + 1 <= n) {
        all -= abs(a[r + 1]);
        a[r + 1] -= x;
        all += abs(a[r + 1]);
        update(1, r, 1, n);
        update(1, r + 1, 1, n);
      }
    }
  }
}

### 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;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3fll;
const long long M = 1e9 + 7;
const long long maxn = 1e5 + 7;
const double eps = 0.00000001;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline T powMM(T a, T b) {
  T ret = 1;
  for (; b; b >>= 1ll, a = 1ll * a * a % M)
    if (b & 1) ret = 1ll * ret * a % M;
  return ret;
}
struct node {
  long long del, sum, add;
} T[maxn << 2];
long long a[maxn];
node merge(const node &A, const node &B) {
  node ret;
  ret.del = max(A.del, B.del);
  ret.sum = max(A.sum, B.sum);
  ret.add = max(A.add, B.add);
  return ret;
}
void update(int x, int pos, int L, int R) {
  if (L == R) {
    T[x].del = a[L + 1] - a[L] - abs(a[L]) - abs(a[L + 1]);
    T[x].add = a[L] - a[L + 1] - abs(a[L]) - abs(a[L + 1]);
    T[x].sum = abs(a[L] + a[L + 1]) - abs(a[L]) - abs(a[L + 1]);
    return;
  }
  int mid = (L + R) / 2;
  if (pos <= mid)
    update(x << 1, pos, L, mid);
  else
    update(x << 1 | 1, pos, mid + 1, R);
  T[x] = merge(T[x << 1], T[x << 1 | 1]);
}
node query(int x, int l, int r, int L, int R) {
  if (l <= L && R <= r) return T[x];
  int mid = (L + R) / 2;
  if (r <= mid)
    return query(x << 1, l, r, L, mid);
  else if (mid < l)
    return query(x << 1 | 1, l, r, mid + 1, R);
  else
    return merge(query(x << 1, l, r, L, mid),
                 query(x << 1 | 1, l, r, mid + 1, R));
}
int n, m, q;
int i, j;
long long all;
int main() {
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%I64d", &a[i]);
  for (i = n; i >= 2; i--) a[i] -= a[i - 1];
  a[1] = 0;
  for (i = 2; i <= n; i++) update(1, i, 1, n), all += abs(a[i]);
  scanf("%d", &q);
  while (q--) {
    int op, l, r, x;
    scanf("%d%d%d%d", &op, &l, &r, &x);
    if (op == 1) {
      long long ans = -INFF;
      if (l == 1) ans = max(ans, abs(a[2] - x) - abs(a[2])), l++;
      if (r == n) ans = max(ans, abs(a[n] + x) - abs(a[n])), r--;
      if (l <= r) {
        node now = query(1, l, r, 1, n);
        ans = max(ans, now.sum);
        ans = max(ans, now.del - 2 * x);
        ans = max(ans, now.add + 2 * x);
      }
      printf("%I64d\n", ans + all);
    } else {
      if (2 <= l) {
        all -= abs(a[l]);
        a[l] += x;
        all += abs(a[l]);
        update(1, l, 1, n);
        update(1, l - 1, 1, n);
      }
      if (r + 1 <= n) {
        all -= abs(a[r + 1]);
        a[r + 1] -= x;
        all += abs(a[r + 1]);
        update(1, r, 1, n);
        update(1, r + 1, 1, n);
      }
    }
  }
}

```