#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const long long inf = 0x3f3f3f3f3f3f3f3f;
long long t, l, r, x;
long long n, q, a[N], b[N], del[N], tree[N * 4][5];
int read() {
  int x = 0;
  char c = getchar();
  while (c > '9' || c < '0') c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x;
}
void Build(int x, int l, int r) {
  if (l == r) {
    tree[x][1] = abs(del[l]);
    tree[x][2] = 0;
    tree[x][3] = tree[x][4] = inf;
    if (a[l] >= a[l - 1] && a[l] >= a[l + 1])
      tree[x][2] = 1;
    else if (a[l] < a[l - 1] && a[l] < a[l + 1])
      tree[x][3] = a[l - 1] + a[l + 1] - a[l] - a[l];
    else
      tree[x][4] = max(a[l - 1], a[l + 1]) - a[l];
    return;
  }
  int mid = (l + r) >> 1;
  Build(x << 1, l, mid);
  Build(x << 1 | 1, mid + 1, r);
  tree[x][1] = tree[x << 1][1] + tree[x << 1 | 1][1];
  tree[x][2] = tree[x << 1][2] + tree[x << 1 | 1][2];
  tree[x][3] = min(tree[x << 1][3], tree[x << 1 | 1][3]);
  tree[x][4] = min(tree[x << 1][4], tree[x << 1 | 1][4]);
}
void Updata(int x, int to, int lt, int rt) {
  if (lt == rt) {
    if (lt == l - 1)
      tree[x][1] = abs(del[l - 1]);
    else if (lt == r)
      tree[x][1] = abs(del[r]);
    tree[x][2] = 0;
    tree[x][3] = tree[x][4] = inf;
    if (del[lt - 1] >= 0 && del[lt] <= 0)
      tree[x][2] = 1;
    else if (del[lt - 1] < 0 && del[lt] > 0)
      tree[x][3] = del[lt] - del[lt - 1];
    else if (del[lt - 1] < 0)
      tree[x][4] = -del[lt - 1];
    else
      tree[x][4] = del[lt];
    return;
  }
  int mid = (lt + rt) >> 1;
  if (to <= mid)
    Updata(x << 1, to, lt, mid);
  else
    Updata(x << 1 | 1, to, mid + 1, rt);
  tree[x][1] = tree[x << 1][1] + tree[x << 1 | 1][1];
  tree[x][2] = tree[x << 1][2] + tree[x << 1 | 1][2];
  tree[x][3] = min(tree[x << 1][3], tree[x << 1 | 1][3]);
  tree[x][4] = min(tree[x << 1][4], tree[x << 1 | 1][4]);
}
void Query(int x, int l, int r, int lt, int rt) {
  if (l == lt && r == rt) {
    a[1] += tree[x][1];
    a[2] += tree[x][2];
    a[3] = min(a[3], tree[x][3]);
    a[4] = min(a[4], tree[x][4]);
    return;
  }
  int mid = (l + r) >> 1;
  if (mid >= rt)
    Query(x << 1, l, mid, lt, rt);
  else if (mid < lt)
    Query(x << 1 | 1, mid + 1, r, lt, rt);
  else
    Query(x << 1, l, mid, lt, mid), Query(x << 1 | 1, mid + 1, r, mid + 1, rt);
}
int main() {
  n = read();
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    del[i - 1] = a[i] - a[i - 1];
  }
  Build(1, 1, n);
  q = read();
  for (int i = 1; i <= q; i++) {
    t = read(), l = read(), r = read(), x = read();
    if (t == 1) {
      long long ans = -inf;
      a[1] = a[2] = 0, a[3] = a[4] = inf;
      Query(1, 1, n, max((long long)2, l), min(n - 1, r));
      for (int i = 1; i <= 4; i++) b[i] = a[i];
      a[1] = a[2] = 0, a[3] = a[4] = inf;
      Query(1, 1, n, 1, n - 1);
      if (b[2]) ans = x * 2;
      if (b[3] <= x)
        ans = max(ans, (x - b[3]) * 2);
      else if (l == r) {
        long long u = abs(del[l - 1]), v = abs(del[l]);
        if (u > v) swap(u, v);
        if (x <= u)
          ans = max(ans, -2 * x);
        else if (x <= v)
          ans = max(ans, -2 * u);
        else
          ans = max(ans, -2 * (u + v - x));
      }
      if (b[4] <= x)
        ans = max(ans, (x - b[4]) * 2);
      else if (b[4] < inf)
        ans = max(ans, (long long)0);
      if (l == 1) {
        if (del[1] <= 0)
          ans = max(ans, x);
        else
          ans = max(ans, x - del[1]);
      }
      if (r == n) {
        if (a[r - 1] <= 0)
          ans = max(ans, x);
        else
          ans = max(ans, x - del[r - 1]);
      }
      printf("%lld\n", a[1] + ans);
    } else {
      del[l - 1] += x;
      del[r] -= x;
      Updata(1, l - 1, 1, n);
      Updata(1, l, 1, n);
      Updata(1, r, 1, n);
      Updata(1, r + 1, 1, n);
    }
  }
}

### 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 + 10;
const long long inf = 0x3f3f3f3f3f3f3f3f;
long long t, l, r, x;
long long n, q, a[N], b[N], del[N], tree[N * 4][5];
int read() {
  int x = 0;
  char c = getchar();
  while (c > '9' || c < '0') c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x;
}
void Build(int x, int l, int r) {
  if (l == r) {
    tree[x][1] = abs(del[l]);
    tree[x][2] = 0;
    tree[x][3] = tree[x][4] = inf;
    if (a[l] >= a[l - 1] && a[l] >= a[l + 1])
      tree[x][2] = 1;
    else if (a[l] < a[l - 1] && a[l] < a[l + 1])
      tree[x][3] = a[l - 1] + a[l + 1] - a[l] - a[l];
    else
      tree[x][4] = max(a[l - 1], a[l + 1]) - a[l];
    return;
  }
  int mid = (l + r) >> 1;
  Build(x << 1, l, mid);
  Build(x << 1 | 1, mid + 1, r);
  tree[x][1] = tree[x << 1][1] + tree[x << 1 | 1][1];
  tree[x][2] = tree[x << 1][2] + tree[x << 1 | 1][2];
  tree[x][3] = min(tree[x << 1][3], tree[x << 1 | 1][3]);
  tree[x][4] = min(tree[x << 1][4], tree[x << 1 | 1][4]);
}
void Updata(int x, int to, int lt, int rt) {
  if (lt == rt) {
    if (lt == l - 1)
      tree[x][1] = abs(del[l - 1]);
    else if (lt == r)
      tree[x][1] = abs(del[r]);
    tree[x][2] = 0;
    tree[x][3] = tree[x][4] = inf;
    if (del[lt - 1] >= 0 && del[lt] <= 0)
      tree[x][2] = 1;
    else if (del[lt - 1] < 0 && del[lt] > 0)
      tree[x][3] = del[lt] - del[lt - 1];
    else if (del[lt - 1] < 0)
      tree[x][4] = -del[lt - 1];
    else
      tree[x][4] = del[lt];
    return;
  }
  int mid = (lt + rt) >> 1;
  if (to <= mid)
    Updata(x << 1, to, lt, mid);
  else
    Updata(x << 1 | 1, to, mid + 1, rt);
  tree[x][1] = tree[x << 1][1] + tree[x << 1 | 1][1];
  tree[x][2] = tree[x << 1][2] + tree[x << 1 | 1][2];
  tree[x][3] = min(tree[x << 1][3], tree[x << 1 | 1][3]);
  tree[x][4] = min(tree[x << 1][4], tree[x << 1 | 1][4]);
}
void Query(int x, int l, int r, int lt, int rt) {
  if (l == lt && r == rt) {
    a[1] += tree[x][1];
    a[2] += tree[x][2];
    a[3] = min(a[3], tree[x][3]);
    a[4] = min(a[4], tree[x][4]);
    return;
  }
  int mid = (l + r) >> 1;
  if (mid >= rt)
    Query(x << 1, l, mid, lt, rt);
  else if (mid < lt)
    Query(x << 1 | 1, mid + 1, r, lt, rt);
  else
    Query(x << 1, l, mid, lt, mid), Query(x << 1 | 1, mid + 1, r, mid + 1, rt);
}
int main() {
  n = read();
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    del[i - 1] = a[i] - a[i - 1];
  }
  Build(1, 1, n);
  q = read();
  for (int i = 1; i <= q; i++) {
    t = read(), l = read(), r = read(), x = read();
    if (t == 1) {
      long long ans = -inf;
      a[1] = a[2] = 0, a[3] = a[4] = inf;
      Query(1, 1, n, max((long long)2, l), min(n - 1, r));
      for (int i = 1; i <= 4; i++) b[i] = a[i];
      a[1] = a[2] = 0, a[3] = a[4] = inf;
      Query(1, 1, n, 1, n - 1);
      if (b[2]) ans = x * 2;
      if (b[3] <= x)
        ans = max(ans, (x - b[3]) * 2);
      else if (l == r) {
        long long u = abs(del[l - 1]), v = abs(del[l]);
        if (u > v) swap(u, v);
        if (x <= u)
          ans = max(ans, -2 * x);
        else if (x <= v)
          ans = max(ans, -2 * u);
        else
          ans = max(ans, -2 * (u + v - x));
      }
      if (b[4] <= x)
        ans = max(ans, (x - b[4]) * 2);
      else if (b[4] < inf)
        ans = max(ans, (long long)0);
      if (l == 1) {
        if (del[1] <= 0)
          ans = max(ans, x);
        else
          ans = max(ans, x - del[1]);
      }
      if (r == n) {
        if (a[r - 1] <= 0)
          ans = max(ans, x);
        else
          ans = max(ans, x - del[r - 1]);
      }
      printf("%lld\n", a[1] + ans);
    } else {
      del[l - 1] += x;
      del[r] -= x;
      Updata(1, l - 1, 1, n);
      Updata(1, l, 1, n);
      Updata(1, r, 1, n);
      Updata(1, r + 1, 1, n);
    }
  }
}

```