#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, Q;
int a[N];
long long c[N];
struct Node {
  int l, r;
  long long Min;
} tree[N << 2];
void push_up(int i) {
  tree[i].Min = min(tree[i * 2].Min, tree[i * 2 + 1].Min);
  return;
}
void build(int i, int l, int r) {
  tree[i].l = l, tree[i].r = r;
  if (l == r) {
    tree[i].Min = max(0LL, c[l - 1]) + max(0LL, -c[l]);
    return;
  }
  int mid = (l + r) / 2;
  build(i * 2, l, mid);
  build(i * 2 + 1, mid + 1, r);
  push_up(i);
  return;
}
long long ans;
void modify(int i, int u, int v) {
  if (tree[i].l == tree[i].r) {
    ans += -abs(c[u]) + abs(c[u] + v);
    c[u] += v;
    tree[i].Min = max(0LL, c[u - 1]) + max(0LL, -c[u]);
    if (v && u + 1 <= n - 1) modify(1, u + 1, 0);
    return;
  }
  if (u <= tree[i * 2].r)
    modify(i * 2, u, v);
  else
    modify(i * 2 + 1, u, v);
  push_up(i);
  return;
}
long long query(int i, int l, int r) {
  if (l <= tree[i].l && tree[i].r <= r) return tree[i].Min;
  if (r <= tree[i * 2].r)
    return query(i * 2, l, r);
  else if (l >= tree[i * 2 + 1].l)
    return query(i * 2 + 1, l, r);
  else
    return min(query(i * 2, l, r), query(i * 2 + 1, l, r));
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) c[i] = a[i] - a[i + 1];
  for (int i = 1; i <= n - 1; i++) ans += abs(c[i]);
  build(1, 2, n - 1);
  scanf("%d", &Q);
  while (Q--) {
    int t, l, r, x;
    scanf("%d%d%d%d", &t, &l, &r, &x);
    if (t == 1) {
      if (l == r) {
        if (l == 1)
          printf("%lld\n", ans - abs(c[l]) + abs(c[l] + x));
        else if (l == n)
          printf("%lld\n", ans - abs(c[l - 1]) + abs(c[l - 1] - x));
        else
          printf("%lld\n", ans - abs(c[l - 1]) - abs(c[l]) + abs(c[l - 1] - x) +
                               abs(c[l] + x));
      } else {
        long long del = 2 * (x - query(1, max(l, 2), min(r, n - 1)));
        if (l == 1) del = max(del, (long long)-abs(c[l]) + abs(c[l] + x));
        if (r == n)
          del = max(del, (long long)-abs(c[r - 1]) + abs(c[r - 1] - x));
        printf("%lld\n", ans + max(0LL, del));
      }
    } else if (t == 2) {
      if (r == n)
        ans += -abs(c[n - 1]) + abs(c[n - 1] - x), c[n - 1] -= x,
            modify(1, n - 1, 0);
      else
        modify(1, r, x);
      if (l == 1)
        continue;
      else if (l == 2)
        ans += -abs(c[1]) + abs(c[1] - x), c[1] -= x, modify(1, 2, 0);
      else
        modify(1, l - 1, -x);
    }
  }
  return 0;
}

### Prompt

Please create a solution in CPP 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 = 100005;
int n, Q;
int a[N];
long long c[N];
struct Node {
  int l, r;
  long long Min;
} tree[N << 2];
void push_up(int i) {
  tree[i].Min = min(tree[i * 2].Min, tree[i * 2 + 1].Min);
  return;
}
void build(int i, int l, int r) {
  tree[i].l = l, tree[i].r = r;
  if (l == r) {
    tree[i].Min = max(0LL, c[l - 1]) + max(0LL, -c[l]);
    return;
  }
  int mid = (l + r) / 2;
  build(i * 2, l, mid);
  build(i * 2 + 1, mid + 1, r);
  push_up(i);
  return;
}
long long ans;
void modify(int i, int u, int v) {
  if (tree[i].l == tree[i].r) {
    ans += -abs(c[u]) + abs(c[u] + v);
    c[u] += v;
    tree[i].Min = max(0LL, c[u - 1]) + max(0LL, -c[u]);
    if (v && u + 1 <= n - 1) modify(1, u + 1, 0);
    return;
  }
  if (u <= tree[i * 2].r)
    modify(i * 2, u, v);
  else
    modify(i * 2 + 1, u, v);
  push_up(i);
  return;
}
long long query(int i, int l, int r) {
  if (l <= tree[i].l && tree[i].r <= r) return tree[i].Min;
  if (r <= tree[i * 2].r)
    return query(i * 2, l, r);
  else if (l >= tree[i * 2 + 1].l)
    return query(i * 2 + 1, l, r);
  else
    return min(query(i * 2, l, r), query(i * 2 + 1, l, r));
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++) c[i] = a[i] - a[i + 1];
  for (int i = 1; i <= n - 1; i++) ans += abs(c[i]);
  build(1, 2, n - 1);
  scanf("%d", &Q);
  while (Q--) {
    int t, l, r, x;
    scanf("%d%d%d%d", &t, &l, &r, &x);
    if (t == 1) {
      if (l == r) {
        if (l == 1)
          printf("%lld\n", ans - abs(c[l]) + abs(c[l] + x));
        else if (l == n)
          printf("%lld\n", ans - abs(c[l - 1]) + abs(c[l - 1] - x));
        else
          printf("%lld\n", ans - abs(c[l - 1]) - abs(c[l]) + abs(c[l - 1] - x) +
                               abs(c[l] + x));
      } else {
        long long del = 2 * (x - query(1, max(l, 2), min(r, n - 1)));
        if (l == 1) del = max(del, (long long)-abs(c[l]) + abs(c[l] + x));
        if (r == n)
          del = max(del, (long long)-abs(c[r - 1]) + abs(c[r - 1] - x));
        printf("%lld\n", ans + max(0LL, del));
      }
    } else if (t == 2) {
      if (r == n)
        ans += -abs(c[n - 1]) + abs(c[n - 1] - x), c[n - 1] -= x,
            modify(1, n - 1, 0);
      else
        modify(1, r, x);
      if (l == 1)
        continue;
      else if (l == 2)
        ans += -abs(c[1]) + abs(c[1] - x), c[1] -= x, modify(1, 2, 0);
      else
        modify(1, l - 1, -x);
    }
  }
  return 0;
}

```