#include <bits/stdc++.h>
using namespace std;
struct data {
  long long int v, p, mn[2];
  int i[2];
} tr[100005 << 2];
long long int a[100005], sum;
void init(int n, int b, int e) {
  if (b == e) {
    tr[n].p = 0;
    tr[n].v = a[b];
    tr[n].mn[0] = tr[n].mn[1] = max(a[b - 1], a[b + 1]) - a[b];
    tr[n].i[1] = tr[n].i[0] = b;
    if (min(a[b - 1], a[b + 1]) > a[b])
      tr[n].mn[0] = tr[n].mn[1] = 1000000000000000000;
    return;
  }
  tr[n].p = 0;
  int l, m, r;
  m = (b + e) >> 1;
  l = n << 1;
  r = l + 1;
  init(l, b, m);
  init(r, m + 1, e);
  if (tr[l].mn[0] < tr[r].mn[0]) {
    tr[n].mn[0] = tr[l].mn[0];
    tr[n].i[0] = tr[l].i[0];
  } else {
    tr[n].mn[0] = tr[r].mn[0];
    tr[n].i[0] = tr[r].i[0];
  }
  if (tr[l].mn[1] > tr[r].mn[1]) {
    tr[n].mn[1] = tr[l].mn[1];
    tr[n].i[1] = tr[l].i[1];
  } else {
    tr[n].mn[1] = tr[r].mn[1];
    tr[n].i[1] = tr[r].i[1];
  }
}
data getmin(int n, int b, int e, int i, int j) {
  data tmp, tmp1;
  if (e < i || j < b) {
    tmp.mn[0] = 1000000000000000000;
    tmp.mn[1] = -1000000000000000000;
    tmp.i[0] = -1;
    tmp.i[1] = -1;
    return tmp;
  }
  if (i <= b && j >= e) return tr[n];
  int l, m, r;
  m = (b + e) >> 1;
  l = n << 1;
  r = l + 1;
  tmp = getmin(l, b, m, i, j);
  tmp1 = getmin(r, m + 1, e, i, j);
  if (tmp1.mn[0] < tmp.mn[0] || (tmp1.mn[0] == tmp.mn[0] && tmp.i[0] == -1)) {
    tmp.mn[0] = tmp1.mn[0];
    tmp.i[0] = tmp1.i[0];
  }
  if (tmp1.mn[1] > tmp.mn[1] || (tmp1.mn[1] == tmp.mn[1] && tmp.i[1] == -1)) {
    tmp.mn[1] = tmp1.mn[1];
    tmp.i[1] = tmp1.i[1];
  }
  return tmp;
}
long long int getvalue(int n, int b, int e, int i, long long int c) {
  if (i < b || i > e) return 0;
  if (b == e) {
    return tr[n].v + c;
  }
  int l, m, r;
  m = (b + e) >> 1;
  l = n << 1;
  r = l + 1;
  c += tr[n].p;
  return max(getvalue(l, b, m, i, c), getvalue(r, m + 1, e, i, c));
}
void updatevalue(int n, int b, int e, int i, int j, long long int c) {
  if (b > j || e < i) return;
  if (i <= b && j >= e) {
    tr[n].p += c;
    if (b == e) tr[n].v += c;
    return;
  }
  int l, m, r;
  m = (b + e) >> 1;
  l = n << 1;
  r = l + 1;
  updatevalue(l, b, m, i, j, c);
  updatevalue(r, m + 1, e, i, j, c);
}
void updatemin(int n, int b, int e, int i, int nn, long long int c, int j) {
  if (i < b || i > e) return;
  if (b == e) {
    long long int mn, mx;
    if (b == 2)
      mn = a[1];
    else
      mn = getvalue(1, 2, nn - 1, b - 1, 0);
    if (b == (nn - 1))
      mx = a[nn];
    else
      mx = getvalue(1, 2, nn - 1, b + 1, 0);
    tr[n].mn[0] = tr[n].mn[1] = max(mn, mx) - (tr[n].v + c);
    tr[n].i[1] = tr[n].i[0] = i;
    if (min(mn, mx) > (tr[n].v + c))
      tr[n].mn[0] = tr[n].mn[1] = 1000000000000000000;
    if (j == 1)
      sum += abs(tr[n].v + c - mx);
    else if (j == 0)
      sum += abs(tr[n].v + c - mn);
    return;
  }
  int l, m, r;
  m = (b + e) >> 1;
  l = n << 1;
  r = l + 1;
  c += tr[n].p;
  updatemin(l, b, m, i, nn, c, j);
  updatemin(r, m + 1, e, i, nn, c, j);
  if (tr[l].mn[0] < tr[r].mn[0]) {
    tr[n].mn[0] = tr[l].mn[0];
    tr[n].i[0] = tr[l].i[0];
  } else {
    tr[n].mn[0] = tr[r].mn[0];
    tr[n].i[0] = tr[r].i[0];
  }
  if (tr[l].mn[1] > tr[r].mn[1]) {
    tr[n].mn[1] = tr[l].mn[1];
    tr[n].i[1] = tr[l].i[1];
  } else {
    tr[n].mn[1] = tr[r].mn[1];
    tr[n].i[1] = tr[r].i[1];
  }
}
int main() {
  data g;
  int n, i, q, l, r, t;
  long long int x, mn, mx, tmp, tmp1, b;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    if (i > 1) sum += abs(a[i] - a[i - 1]);
  }
  init(1, 2, n - 1);
  scanf("%d", &q);
  while (q--) {
    scanf("%d %d %d %lld", &t, &l, &r, &x);
    if (t == 1) {
      g = getmin(1, 2, n - 1, l, r);
      if (g.mn[0] <= 0)
        printf("%lld\n", sum + (x << 1));
      else {
        if (g.i[0] == 2)
          mn = a[1];
        else
          mn = getvalue(1, 2, n - 1, g.i[0] - 1, 0);
        if (g.i[0] == n - 1)
          mx = a[n];
        else
          mx = getvalue(1, 2, n - 1, g.i[0] + 1, 0);
        b = getvalue(1, 2, n - 1, g.i[0], 0);
        tmp =
            sum - abs(b - mn) - abs(b - mx) + abs(b + x - mn) + abs(b + x - mx);
        if (g.mn[1] < 1000000000000000000 || g.mn[0] == 1000000000000000000)
          printf("%lld\n", tmp);
        else {
          if (g.i[1] == 2)
            mn = a[1];
          else
            mn = getvalue(1, 2, n - 1, g.i[1] - 1, 0);
          if (g.i[1] == n - 1)
            mx = a[n];
          else
            mx = getvalue(1, 2, n - 1, g.i[1] + 1, 0);
          b = getvalue(1, 2, n - 1, g.i[1], 0);
          tmp1 = sum - abs(b - mn) - abs(b - mx) + abs(b + x - mn) +
                 abs(b + x - mx);
          printf("%lld\n", max(tmp, tmp1));
        }
      }
    } else if (t == 2) {
      mn = getvalue(1, 2, n - 1, l, 0);
      if (l == 2)
        mx = a[1];
      else
        mx = getvalue(1, 2, n - 1, l - 1, 0);
      sum -= abs(mn - mx);
      mn = getvalue(1, 2, n - 1, r, 0);
      if (r == (n - 1))
        mx = a[n];
      else
        mx = getvalue(1, 2, n - 1, r + 1, 0);
      sum -= abs(mn - mx);
      updatevalue(1, 2, n - 1, l, r, x);
      updatemin(1, 2, n - 1, l, n, 0, 0);
      updatemin(1, 2, n - 1, r, n, 0, 1);
      if (l > 2) updatemin(1, 2, n - 1, l - 1, n, 0, -1);
      if (r < n - 1) updatemin(1, 2, n - 1, r + 1, n, 0, -1);
    } else {
      if (l == 1)
        cout << a[1] << endl;
      else if (l == n)
        cout << a[n] << endl;
      else {
        printf("%lld\n", getvalue(1, 2, n - 1, l, 0));
        g = getmin(1, 2, n - 1, l, l);
        cout << g.i[0] << " " << g.mn[0] << " " << g.i[1] << " " << g.mn[1]
             << endl;
      }
    }
  }
  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;
struct data {
  long long int v, p, mn[2];
  int i[2];
} tr[100005 << 2];
long long int a[100005], sum;
void init(int n, int b, int e) {
  if (b == e) {
    tr[n].p = 0;
    tr[n].v = a[b];
    tr[n].mn[0] = tr[n].mn[1] = max(a[b - 1], a[b + 1]) - a[b];
    tr[n].i[1] = tr[n].i[0] = b;
    if (min(a[b - 1], a[b + 1]) > a[b])
      tr[n].mn[0] = tr[n].mn[1] = 1000000000000000000;
    return;
  }
  tr[n].p = 0;
  int l, m, r;
  m = (b + e) >> 1;
  l = n << 1;
  r = l + 1;
  init(l, b, m);
  init(r, m + 1, e);
  if (tr[l].mn[0] < tr[r].mn[0]) {
    tr[n].mn[0] = tr[l].mn[0];
    tr[n].i[0] = tr[l].i[0];
  } else {
    tr[n].mn[0] = tr[r].mn[0];
    tr[n].i[0] = tr[r].i[0];
  }
  if (tr[l].mn[1] > tr[r].mn[1]) {
    tr[n].mn[1] = tr[l].mn[1];
    tr[n].i[1] = tr[l].i[1];
  } else {
    tr[n].mn[1] = tr[r].mn[1];
    tr[n].i[1] = tr[r].i[1];
  }
}
data getmin(int n, int b, int e, int i, int j) {
  data tmp, tmp1;
  if (e < i || j < b) {
    tmp.mn[0] = 1000000000000000000;
    tmp.mn[1] = -1000000000000000000;
    tmp.i[0] = -1;
    tmp.i[1] = -1;
    return tmp;
  }
  if (i <= b && j >= e) return tr[n];
  int l, m, r;
  m = (b + e) >> 1;
  l = n << 1;
  r = l + 1;
  tmp = getmin(l, b, m, i, j);
  tmp1 = getmin(r, m + 1, e, i, j);
  if (tmp1.mn[0] < tmp.mn[0] || (tmp1.mn[0] == tmp.mn[0] && tmp.i[0] == -1)) {
    tmp.mn[0] = tmp1.mn[0];
    tmp.i[0] = tmp1.i[0];
  }
  if (tmp1.mn[1] > tmp.mn[1] || (tmp1.mn[1] == tmp.mn[1] && tmp.i[1] == -1)) {
    tmp.mn[1] = tmp1.mn[1];
    tmp.i[1] = tmp1.i[1];
  }
  return tmp;
}
long long int getvalue(int n, int b, int e, int i, long long int c) {
  if (i < b || i > e) return 0;
  if (b == e) {
    return tr[n].v + c;
  }
  int l, m, r;
  m = (b + e) >> 1;
  l = n << 1;
  r = l + 1;
  c += tr[n].p;
  return max(getvalue(l, b, m, i, c), getvalue(r, m + 1, e, i, c));
}
void updatevalue(int n, int b, int e, int i, int j, long long int c) {
  if (b > j || e < i) return;
  if (i <= b && j >= e) {
    tr[n].p += c;
    if (b == e) tr[n].v += c;
    return;
  }
  int l, m, r;
  m = (b + e) >> 1;
  l = n << 1;
  r = l + 1;
  updatevalue(l, b, m, i, j, c);
  updatevalue(r, m + 1, e, i, j, c);
}
void updatemin(int n, int b, int e, int i, int nn, long long int c, int j) {
  if (i < b || i > e) return;
  if (b == e) {
    long long int mn, mx;
    if (b == 2)
      mn = a[1];
    else
      mn = getvalue(1, 2, nn - 1, b - 1, 0);
    if (b == (nn - 1))
      mx = a[nn];
    else
      mx = getvalue(1, 2, nn - 1, b + 1, 0);
    tr[n].mn[0] = tr[n].mn[1] = max(mn, mx) - (tr[n].v + c);
    tr[n].i[1] = tr[n].i[0] = i;
    if (min(mn, mx) > (tr[n].v + c))
      tr[n].mn[0] = tr[n].mn[1] = 1000000000000000000;
    if (j == 1)
      sum += abs(tr[n].v + c - mx);
    else if (j == 0)
      sum += abs(tr[n].v + c - mn);
    return;
  }
  int l, m, r;
  m = (b + e) >> 1;
  l = n << 1;
  r = l + 1;
  c += tr[n].p;
  updatemin(l, b, m, i, nn, c, j);
  updatemin(r, m + 1, e, i, nn, c, j);
  if (tr[l].mn[0] < tr[r].mn[0]) {
    tr[n].mn[0] = tr[l].mn[0];
    tr[n].i[0] = tr[l].i[0];
  } else {
    tr[n].mn[0] = tr[r].mn[0];
    tr[n].i[0] = tr[r].i[0];
  }
  if (tr[l].mn[1] > tr[r].mn[1]) {
    tr[n].mn[1] = tr[l].mn[1];
    tr[n].i[1] = tr[l].i[1];
  } else {
    tr[n].mn[1] = tr[r].mn[1];
    tr[n].i[1] = tr[r].i[1];
  }
}
int main() {
  data g;
  int n, i, q, l, r, t;
  long long int x, mn, mx, tmp, tmp1, b;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    if (i > 1) sum += abs(a[i] - a[i - 1]);
  }
  init(1, 2, n - 1);
  scanf("%d", &q);
  while (q--) {
    scanf("%d %d %d %lld", &t, &l, &r, &x);
    if (t == 1) {
      g = getmin(1, 2, n - 1, l, r);
      if (g.mn[0] <= 0)
        printf("%lld\n", sum + (x << 1));
      else {
        if (g.i[0] == 2)
          mn = a[1];
        else
          mn = getvalue(1, 2, n - 1, g.i[0] - 1, 0);
        if (g.i[0] == n - 1)
          mx = a[n];
        else
          mx = getvalue(1, 2, n - 1, g.i[0] + 1, 0);
        b = getvalue(1, 2, n - 1, g.i[0], 0);
        tmp =
            sum - abs(b - mn) - abs(b - mx) + abs(b + x - mn) + abs(b + x - mx);
        if (g.mn[1] < 1000000000000000000 || g.mn[0] == 1000000000000000000)
          printf("%lld\n", tmp);
        else {
          if (g.i[1] == 2)
            mn = a[1];
          else
            mn = getvalue(1, 2, n - 1, g.i[1] - 1, 0);
          if (g.i[1] == n - 1)
            mx = a[n];
          else
            mx = getvalue(1, 2, n - 1, g.i[1] + 1, 0);
          b = getvalue(1, 2, n - 1, g.i[1], 0);
          tmp1 = sum - abs(b - mn) - abs(b - mx) + abs(b + x - mn) +
                 abs(b + x - mx);
          printf("%lld\n", max(tmp, tmp1));
        }
      }
    } else if (t == 2) {
      mn = getvalue(1, 2, n - 1, l, 0);
      if (l == 2)
        mx = a[1];
      else
        mx = getvalue(1, 2, n - 1, l - 1, 0);
      sum -= abs(mn - mx);
      mn = getvalue(1, 2, n - 1, r, 0);
      if (r == (n - 1))
        mx = a[n];
      else
        mx = getvalue(1, 2, n - 1, r + 1, 0);
      sum -= abs(mn - mx);
      updatevalue(1, 2, n - 1, l, r, x);
      updatemin(1, 2, n - 1, l, n, 0, 0);
      updatemin(1, 2, n - 1, r, n, 0, 1);
      if (l > 2) updatemin(1, 2, n - 1, l - 1, n, 0, -1);
      if (r < n - 1) updatemin(1, 2, n - 1, r + 1, n, 0, -1);
    } else {
      if (l == 1)
        cout << a[1] << endl;
      else if (l == n)
        cout << a[n] << endl;
      else {
        printf("%lld\n", getvalue(1, 2, n - 1, l, 0));
        g = getmin(1, 2, n - 1, l, l);
        cout << g.i[0] << " " << g.mn[0] << " " << g.i[1] << " " << g.mn[1]
             << endl;
      }
    }
  }
  return 0;
}

```