#include <bits/stdc++.h>
const int inf = (1ll << 30) - 1;
const int maxn = (int)1e5 + 10;
using namespace std;
struct node {
  long long a1, a2, a3, a4, sum;
};
node t[400400];
long long d[400400];
long long a[400400];
int n;
node merge(node a, node b) {
  node c;
  c.a1 = max(a.a1, b.a1);
  c.a2 = max(a.a2, b.a2);
  c.a3 = max(a.a3, b.a3);
  c.a4 = max(a.a4, b.a4);
  c.sum = a.sum + b.sum;
  return c;
}
void upd(int v, int tl, int tr, int pos) {
  if (tl == tr) {
    long long C = abs(d[tl]) + abs(d[tl - 1]);
    t[v].a1 = d[tl] + d[tl - 1] - C;
    t[v].a2 = d[tl] - d[tl - 1] - C;
    t[v].a3 = -d[tl] + d[tl - 1] - C;
    t[v].a4 = -d[tl] - d[tl - 1] - C;
    t[v].sum = abs(d[tl]);
    return;
  }
  int mid = (tl + tr) >> 1;
  if (mid >= pos)
    upd(v * 2, tl, mid, pos);
  else
    upd(v * 2 + 1, mid + 1, tr, pos);
  t[v] = merge(t[v * 2], t[v * 2 + 1]);
}
node get(int v, int tl, int tr, int l, int r) {
  if (l <= tl && tr <= r) return t[v];
  int mid = (tl + tr) >> 1;
  if (r <= mid) return get(v * 2, tl, mid, l, r);
  if (mid < l) return get(v * 2 + 1, mid + 1, tr, l, r);
  return merge(get(v * 2, tl, mid, l, r), get(v * 2 + 1, mid + 1, tr, l, r));
}
void build(int v, int tl, int tr) {
  if (tl == tr) {
    long long C = abs(d[tl]) + abs(d[tl - 1]);
    t[v].a1 = d[tl] + d[tl - 1] - C;
    t[v].a2 = d[tl] - d[tl - 1] - C;
    t[v].a3 = -d[tl] + d[tl - 1] - C;
    t[v].a4 = -d[tl] - d[tl - 1] - C;
    t[v].sum = abs(d[tl]);
    return;
  }
  int mid = (tl + tr) >> 1;
  build(v * 2, tl, mid);
  build(v * 2 + 1, mid + 1, tr);
  t[v] = merge(t[v * 2], t[v * 2 + 1]);
}
void solve() {
  scanf("%d", &n);
  for (int i = 1, x; i <= n; i++) {
    scanf("%d", &x);
    a[i] = x;
  }
  long long sum = 0;
  for (int i = 1; i < n; i++) {
    d[i] = a[i] - a[i + 1];
  }
  build(1, 1, n - 1);
  int q;
  scanf("%d", &q);
  for (int i = 0, ty, l, r, x; i < q; i++) {
    scanf("%d%d%d%d", &ty, &l, &r, &x);
    if (ty == 2) {
      d[l - 1] -= x;
      d[r] += x;
      upd(1, 1, n - 1, l - 1);
      upd(1, 1, n - 1, l);
      upd(1, 1, n - 1, r);
      if (r + 1 < n) upd(1, 1, n - 1, r + 1);
    } else {
      node G = get(1, 1, n - 1, l, r);
      long long sum = t[1].sum;
      long long ans =
          max(G.a1, max(max(G.a2 + 2ll * x, G.a3 - 2ll * x), G.a4)) + sum;
      printf("%lld\n", ans);
    }
  }
}
int main() {
  int t = 1;
  for (int i = 1; i <= t; i++) {
    solve();
  }
  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>
const int inf = (1ll << 30) - 1;
const int maxn = (int)1e5 + 10;
using namespace std;
struct node {
  long long a1, a2, a3, a4, sum;
};
node t[400400];
long long d[400400];
long long a[400400];
int n;
node merge(node a, node b) {
  node c;
  c.a1 = max(a.a1, b.a1);
  c.a2 = max(a.a2, b.a2);
  c.a3 = max(a.a3, b.a3);
  c.a4 = max(a.a4, b.a4);
  c.sum = a.sum + b.sum;
  return c;
}
void upd(int v, int tl, int tr, int pos) {
  if (tl == tr) {
    long long C = abs(d[tl]) + abs(d[tl - 1]);
    t[v].a1 = d[tl] + d[tl - 1] - C;
    t[v].a2 = d[tl] - d[tl - 1] - C;
    t[v].a3 = -d[tl] + d[tl - 1] - C;
    t[v].a4 = -d[tl] - d[tl - 1] - C;
    t[v].sum = abs(d[tl]);
    return;
  }
  int mid = (tl + tr) >> 1;
  if (mid >= pos)
    upd(v * 2, tl, mid, pos);
  else
    upd(v * 2 + 1, mid + 1, tr, pos);
  t[v] = merge(t[v * 2], t[v * 2 + 1]);
}
node get(int v, int tl, int tr, int l, int r) {
  if (l <= tl && tr <= r) return t[v];
  int mid = (tl + tr) >> 1;
  if (r <= mid) return get(v * 2, tl, mid, l, r);
  if (mid < l) return get(v * 2 + 1, mid + 1, tr, l, r);
  return merge(get(v * 2, tl, mid, l, r), get(v * 2 + 1, mid + 1, tr, l, r));
}
void build(int v, int tl, int tr) {
  if (tl == tr) {
    long long C = abs(d[tl]) + abs(d[tl - 1]);
    t[v].a1 = d[tl] + d[tl - 1] - C;
    t[v].a2 = d[tl] - d[tl - 1] - C;
    t[v].a3 = -d[tl] + d[tl - 1] - C;
    t[v].a4 = -d[tl] - d[tl - 1] - C;
    t[v].sum = abs(d[tl]);
    return;
  }
  int mid = (tl + tr) >> 1;
  build(v * 2, tl, mid);
  build(v * 2 + 1, mid + 1, tr);
  t[v] = merge(t[v * 2], t[v * 2 + 1]);
}
void solve() {
  scanf("%d", &n);
  for (int i = 1, x; i <= n; i++) {
    scanf("%d", &x);
    a[i] = x;
  }
  long long sum = 0;
  for (int i = 1; i < n; i++) {
    d[i] = a[i] - a[i + 1];
  }
  build(1, 1, n - 1);
  int q;
  scanf("%d", &q);
  for (int i = 0, ty, l, r, x; i < q; i++) {
    scanf("%d%d%d%d", &ty, &l, &r, &x);
    if (ty == 2) {
      d[l - 1] -= x;
      d[r] += x;
      upd(1, 1, n - 1, l - 1);
      upd(1, 1, n - 1, l);
      upd(1, 1, n - 1, r);
      if (r + 1 < n) upd(1, 1, n - 1, r + 1);
    } else {
      node G = get(1, 1, n - 1, l, r);
      long long sum = t[1].sum;
      long long ans =
          max(G.a1, max(max(G.a2 + 2ll * x, G.a3 - 2ll * x), G.a4)) + sum;
      printf("%lld\n", ans);
    }
  }
}
int main() {
  int t = 1;
  for (int i = 1; i <= t; i++) {
    solve();
  }
  return 0;
}

```