#include <bits/stdc++.h>
using namespace std;
long long tree[100010 * 4], ans;
int n, m;
long long a[100010];
long long absx(long long x) { return x > 0 ? x : -x; }
void build(int id, int l, int r) {
  if (l == r) {
    ans += absx(a[l]);
    if (l != 1) tree[id] = max(0ll, -a[l - 1]) + max(0ll, a[l]);
    return;
  }
  int mid = (l + r) >> 1;
  build(id << 1, l, mid);
  build(id << 1 | 1, mid + 1, r);
  tree[id] = min(tree[id << 1], tree[id << 1 | 1]);
}
void add(int id, int l, int r, int pos, long long x) {
  if (l == r) {
    ans -= absx(a[l]);
    a[l] += x;
    ans += absx(a[l]);
    if (pos > 1) tree[id] = max(0ll, -a[l - 1]) + max(0ll, a[l]);
    if (x != 0 && pos < n - 1) add(1, 1, n - 1, pos + 1, 0);
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    add(id << 1, l, mid, pos, x);
  else
    add(id << 1 | 1, mid + 1, r, pos, x);
  tree[id] = min(tree[id << 1], tree[id << 1 | 1]);
}
long long query(int id, int l, int r, int l1, int r1) {
  if (l >= l1 && r <= r1) return tree[id];
  int mid = (l + r) >> 1;
  long long res = 1e18;
  if (l1 <= mid) res = min(res, query(id << 1, l, mid, l1, r1));
  if (r1 > mid) res = min(res, query(id << 1 | 1, mid + 1, r, l1, r1));
  return res;
}
int main() {
  int tag, l, r;
  long long x;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i < n; i++) a[i] = a[i + 1] - a[i];
  build(1, 1, n - 1);
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d%lld", &tag, &l, &r, &x);
    if (tag == 1) {
      if (l == r) {
        if (l == 1)
          printf("%lld\n", ans - absx(a[1]) + absx(a[1] - x));
        else if (l == n)
          printf("%lld\n", ans - absx(a[n - 1]) + absx(a[n - 1] + x));
        else
          printf("%lld\n", ans - absx(a[l - 1]) + absx(a[l - 1] + x) -
                               absx(a[l]) + absx(a[l] - x));
      } else {
        long long res = max(0ll, 2 * x - 2 * query(1, 1, n - 1, max(2, l), r));
        if (l == 1) res = max(res, -absx(a[1]) + absx(a[1] - x));
        if (r == n) res = max(res, -absx(a[n - 1]) + absx(a[n - 1] + x));
        printf("%lld\n", ans + res);
      }
    } else {
      if (l != 1) add(1, 1, n - 1, l - 1, x);
      if (r != n) add(1, 1, n - 1, r, -x);
    }
  }
}

### Prompt

Please formulate 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;
long long tree[100010 * 4], ans;
int n, m;
long long a[100010];
long long absx(long long x) { return x > 0 ? x : -x; }
void build(int id, int l, int r) {
  if (l == r) {
    ans += absx(a[l]);
    if (l != 1) tree[id] = max(0ll, -a[l - 1]) + max(0ll, a[l]);
    return;
  }
  int mid = (l + r) >> 1;
  build(id << 1, l, mid);
  build(id << 1 | 1, mid + 1, r);
  tree[id] = min(tree[id << 1], tree[id << 1 | 1]);
}
void add(int id, int l, int r, int pos, long long x) {
  if (l == r) {
    ans -= absx(a[l]);
    a[l] += x;
    ans += absx(a[l]);
    if (pos > 1) tree[id] = max(0ll, -a[l - 1]) + max(0ll, a[l]);
    if (x != 0 && pos < n - 1) add(1, 1, n - 1, pos + 1, 0);
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    add(id << 1, l, mid, pos, x);
  else
    add(id << 1 | 1, mid + 1, r, pos, x);
  tree[id] = min(tree[id << 1], tree[id << 1 | 1]);
}
long long query(int id, int l, int r, int l1, int r1) {
  if (l >= l1 && r <= r1) return tree[id];
  int mid = (l + r) >> 1;
  long long res = 1e18;
  if (l1 <= mid) res = min(res, query(id << 1, l, mid, l1, r1));
  if (r1 > mid) res = min(res, query(id << 1 | 1, mid + 1, r, l1, r1));
  return res;
}
int main() {
  int tag, l, r;
  long long x;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i < n; i++) a[i] = a[i + 1] - a[i];
  build(1, 1, n - 1);
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d%lld", &tag, &l, &r, &x);
    if (tag == 1) {
      if (l == r) {
        if (l == 1)
          printf("%lld\n", ans - absx(a[1]) + absx(a[1] - x));
        else if (l == n)
          printf("%lld\n", ans - absx(a[n - 1]) + absx(a[n - 1] + x));
        else
          printf("%lld\n", ans - absx(a[l - 1]) + absx(a[l - 1] + x) -
                               absx(a[l]) + absx(a[l] - x));
      } else {
        long long res = max(0ll, 2 * x - 2 * query(1, 1, n - 1, max(2, l), r));
        if (l == 1) res = max(res, -absx(a[1]) + absx(a[1] - x));
        if (r == n) res = max(res, -absx(a[n - 1]) + absx(a[n - 1] + x));
        printf("%lld\n", ans + res);
      }
    } else {
      if (l != 1) add(1, 1, n - 1, l - 1, x);
      if (r != n) add(1, 1, n - 1, r, -x);
    }
  }
}

```