#include <bits/stdc++.h>
using namespace std;
struct segm {
  long long data[100011 * 4 + 1];
  segm() { memset(data, 0, sizeof(data)); }
  void upd(int node, int l, int r, int pos, long long v) {
    if (l == r) {
      data[node] = v;
      return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
      upd((node << 1), l, mid, pos, v);
    else
      upd(((node << 1) | 1), mid + 1, r, pos, v);
    data[node] = min(data[(node << 1)], data[((node << 1) | 1)]);
  }
  long long que(int node, int l, int r, int qL, int qR) {
    if (qL <= l && r <= qR) return data[node];
    int mid = (l + r) >> 1;
    long long ans = 1LL << 60;
    if (qL <= mid) ans = min(ans, que((node << 1), l, mid, qL, qR));
    if (qR > mid) ans = min(ans, que(((node << 1) | 1), mid + 1, r, qL, qR));
    return ans;
  }
};
long long n, q, i, tp, l, r, x;
long long a[100011];
long long aib[100011], act;
long long dif_l[100011];
long long dif_r[100011];
segm work;
long long zrs(long long x) { return (x ^ (x - 1)) & x; }
void upd(long long x, long long v) {
  while (x <= n) {
    aib[x] += v;
    x += zrs(x);
  }
}
long long sum(long long x) {
  long long ans = 0;
  while (x > 0) {
    ans += aib[x];
    x -= zrs(x);
  }
  return ans;
}
long long abss(long long x) {
  if (x < 0) return -x;
  return x;
}
void refresh(int pos) {
  int pre = sum(pos);
  int nxt = sum(pos + 1);
  dif_l[pos] = max(0LL, sum(pos) - sum(pos + 1));
  dif_r[pos] = max(0LL, sum(pos + 1) - sum(pos));
  for (int i = max(1, pos - 1); i <= min(n - 2, 1LL * pos); i++) {
    work.upd(1, 1, n, i, dif_l[i] + dif_r[i + 1]);
  }
}
void update() {
  int pre, nxt;
  if (l > 1) act -= abss(sum(l) - sum(l - 1));
  if (r + 1 <= n) act -= abss(sum(r) - sum(r + 1));
  upd(l, +x);
  upd(r + 1, -x);
  if (l > 1) act += abss(sum(l) - sum(l - 1));
  if (r + 1 <= n) act += abss(sum(r) - sum(r + 1));
  refresh(l - 1);
  refresh(r);
}
long long check(long long pos) {
  long long ans = act;
  if (pos > 1) ans -= abss(sum(pos - 1) - sum(pos));
  if (pos + 1 <= n) ans -= abss(sum(pos + 1) - sum(pos));
  upd(pos, +x);
  upd(pos + 1, -x);
  if (pos > 1) ans += abss(sum(pos - 1) - sum(pos));
  if (pos + 1 <= n) ans += abss(sum(pos + 1) - sum(pos));
  upd(pos, -x);
  upd(pos + 1, +x);
  return ans;
}
long long query() {
  long long ans = max(check(l), check(r));
  if (r - l + 1 >= 3)
    ans = max(ans, act + 2LL * x - 2LL * work.que(1, 1, n, l, r - 2));
  return ans;
}
int main() {
  scanf("%lld", &n);
  for (i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    upd(i, a[i] - a[i - 1]);
    if (i > 1) act += abss(a[i] - a[i - 1]);
  }
  for (i = 1; i < n; i++) {
    dif_l[i] = max(0LL, a[i] - a[i + 1]);
    dif_r[i] = max(0LL, a[i + 1] - a[i]);
  }
  for (i = 1; i + 2 <= n; i++) work.upd(1, 1, n, i, dif_l[i] + dif_r[i + 1]);
  scanf("%lld", &q);
  for (i = 1; i <= q; i++) {
    scanf("%lld%lld%lld%lld", &tp, &l, &r, &x);
    if (tp == 1)
      printf("%lld\n", query());
    else
      update();
  }
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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 segm {
  long long data[100011 * 4 + 1];
  segm() { memset(data, 0, sizeof(data)); }
  void upd(int node, int l, int r, int pos, long long v) {
    if (l == r) {
      data[node] = v;
      return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
      upd((node << 1), l, mid, pos, v);
    else
      upd(((node << 1) | 1), mid + 1, r, pos, v);
    data[node] = min(data[(node << 1)], data[((node << 1) | 1)]);
  }
  long long que(int node, int l, int r, int qL, int qR) {
    if (qL <= l && r <= qR) return data[node];
    int mid = (l + r) >> 1;
    long long ans = 1LL << 60;
    if (qL <= mid) ans = min(ans, que((node << 1), l, mid, qL, qR));
    if (qR > mid) ans = min(ans, que(((node << 1) | 1), mid + 1, r, qL, qR));
    return ans;
  }
};
long long n, q, i, tp, l, r, x;
long long a[100011];
long long aib[100011], act;
long long dif_l[100011];
long long dif_r[100011];
segm work;
long long zrs(long long x) { return (x ^ (x - 1)) & x; }
void upd(long long x, long long v) {
  while (x <= n) {
    aib[x] += v;
    x += zrs(x);
  }
}
long long sum(long long x) {
  long long ans = 0;
  while (x > 0) {
    ans += aib[x];
    x -= zrs(x);
  }
  return ans;
}
long long abss(long long x) {
  if (x < 0) return -x;
  return x;
}
void refresh(int pos) {
  int pre = sum(pos);
  int nxt = sum(pos + 1);
  dif_l[pos] = max(0LL, sum(pos) - sum(pos + 1));
  dif_r[pos] = max(0LL, sum(pos + 1) - sum(pos));
  for (int i = max(1, pos - 1); i <= min(n - 2, 1LL * pos); i++) {
    work.upd(1, 1, n, i, dif_l[i] + dif_r[i + 1]);
  }
}
void update() {
  int pre, nxt;
  if (l > 1) act -= abss(sum(l) - sum(l - 1));
  if (r + 1 <= n) act -= abss(sum(r) - sum(r + 1));
  upd(l, +x);
  upd(r + 1, -x);
  if (l > 1) act += abss(sum(l) - sum(l - 1));
  if (r + 1 <= n) act += abss(sum(r) - sum(r + 1));
  refresh(l - 1);
  refresh(r);
}
long long check(long long pos) {
  long long ans = act;
  if (pos > 1) ans -= abss(sum(pos - 1) - sum(pos));
  if (pos + 1 <= n) ans -= abss(sum(pos + 1) - sum(pos));
  upd(pos, +x);
  upd(pos + 1, -x);
  if (pos > 1) ans += abss(sum(pos - 1) - sum(pos));
  if (pos + 1 <= n) ans += abss(sum(pos + 1) - sum(pos));
  upd(pos, -x);
  upd(pos + 1, +x);
  return ans;
}
long long query() {
  long long ans = max(check(l), check(r));
  if (r - l + 1 >= 3)
    ans = max(ans, act + 2LL * x - 2LL * work.que(1, 1, n, l, r - 2));
  return ans;
}
int main() {
  scanf("%lld", &n);
  for (i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    upd(i, a[i] - a[i - 1]);
    if (i > 1) act += abss(a[i] - a[i - 1]);
  }
  for (i = 1; i < n; i++) {
    dif_l[i] = max(0LL, a[i] - a[i + 1]);
    dif_r[i] = max(0LL, a[i + 1] - a[i]);
  }
  for (i = 1; i + 2 <= n; i++) work.upd(1, 1, n, i, dif_l[i] + dif_r[i + 1]);
  scanf("%lld", &q);
  for (i = 1; i <= q; i++) {
    scanf("%lld%lld%lld%lld", &tp, &l, &r, &x);
    if (tp == 1)
      printf("%lld\n", query());
    else
      update();
  }
  return 0;
}

```