#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
const double eps = 1e-8;
inline void read(int &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= f;
}
inline void read(long long &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= f;
}
const int N = 100010;
int n, m;
long long ans = 0;
long long a[N];
struct P {
  long long l, m, r, v;
} b[N];
long long c[N];
const int ALL = N << 2;
long long ma[ALL], laz[ALL];
void Build(int u, int l, int r) {
  if (l == r) {
    ma[u] = b[l].v;
    return;
  }
  Build((u << 1), l, ((l + r) >> 1));
  Build(((u << 1) | 1), ((l + r) >> 1) + 1, r);
  ma[u] = max(ma[(u << 1)], ma[((u << 1) | 1)]);
}
void Modify(int u, int l, int r, int x, long long v) {
  if (l == r) {
    ma[u] = b[l].v;
    return;
  }
  if (((l + r) >> 1) >= x) Modify((u << 1), l, ((l + r) >> 1), x, v);
  if (((l + r) >> 1) < x) Modify(((u << 1) | 1), ((l + r) >> 1) + 1, r, x, v);
  ma[u] = max(ma[(u << 1)], ma[((u << 1) | 1)]);
}
long long Query(int u, int l, int r, int L, int R) {
  if (L <= l && r <= R) return ma[u];
  long long ret = -INF;
  if (((l + r) >> 1) >= L)
    ret = max(ret, Query((u << 1), l, ((l + r) >> 1), L, R));
  if (((l + r) >> 1) < R)
    ret = max(ret, Query(((u << 1) | 1), ((l + r) >> 1) + 1, r, L, R));
  return ret;
}
inline void Update(int p) {
  b[p].v = min(0ll, b[p].m - b[p].l) + min(0ll, b[p].m - b[p].r);
  Modify(1, 1, n, p, b[p].v);
}
int main() {
  read(n);
  for (int i = 1; i <= n; i++) read(a[i]), b[i].m = a[i];
  for (int i = 1; i < n; i++)
    c[i] = a[i] - a[i + 1], ans += abs(a[i] - a[i + 1]);
  for (int i = 1; i < n; i++)
    b[i].v += min(0ll, a[i] - a[i + 1]), b[i].r = a[i + 1];
  for (int i = 2; i <= n; i++)
    b[i].v += min(0ll, a[i] - a[i - 1]), b[i].l = a[i - 1];
  Build(1, 1, n);
  read(m);
  for (int i = 1; i <= m; i++) {
    long long Ans = 0, res = 0, ret = 0;
    int type, l, r;
    long long x;
    read(type);
    read(l);
    read(r);
    read(x);
    if (type == 1) {
      if (l == 1) {
        res = max(res, abs(c[1] + x));
        l = 2;
      }
      if (r == n) {
        res = max(res, abs(c[n - 1] - x));
        r = n - 1;
      }
      if (l == r) {
        ret =
            ans - abs(c[l - 1]) + abs(c[l - 1] - x) - abs(c[l]) + abs(c[l] + x);
      } else if (l <= r) {
        ret = ans + max(0ll, 2 * Query(1, 1, n, l, r) + 2 * x);
      }
      Ans = max(ret, res);
      printf("%I64d\n", Ans);
    } else {
      ans = ans - abs(c[l - 1]) + abs(c[l - 1] - x);
      c[l - 1] -= x;
      if (l - 1 >= 0) {
        b[l - 1].r += x;
        Update(l - 1);
        b[l].l -= x;
        Update(l);
      }
      ans = ans - abs(c[r]) + abs(c[r] + x);
      c[r] += x;
      if (r + 1 <= n) {
        b[r].r -= x;
        Update(r);
        b[r + 1].l += x;
        Update(r + 1);
      }
    }
  }
  return 0;
}

### Prompt

Your task is to create 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 INF = 2e9;
const double eps = 1e-8;
inline void read(int &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= f;
}
inline void read(long long &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= f;
}
const int N = 100010;
int n, m;
long long ans = 0;
long long a[N];
struct P {
  long long l, m, r, v;
} b[N];
long long c[N];
const int ALL = N << 2;
long long ma[ALL], laz[ALL];
void Build(int u, int l, int r) {
  if (l == r) {
    ma[u] = b[l].v;
    return;
  }
  Build((u << 1), l, ((l + r) >> 1));
  Build(((u << 1) | 1), ((l + r) >> 1) + 1, r);
  ma[u] = max(ma[(u << 1)], ma[((u << 1) | 1)]);
}
void Modify(int u, int l, int r, int x, long long v) {
  if (l == r) {
    ma[u] = b[l].v;
    return;
  }
  if (((l + r) >> 1) >= x) Modify((u << 1), l, ((l + r) >> 1), x, v);
  if (((l + r) >> 1) < x) Modify(((u << 1) | 1), ((l + r) >> 1) + 1, r, x, v);
  ma[u] = max(ma[(u << 1)], ma[((u << 1) | 1)]);
}
long long Query(int u, int l, int r, int L, int R) {
  if (L <= l && r <= R) return ma[u];
  long long ret = -INF;
  if (((l + r) >> 1) >= L)
    ret = max(ret, Query((u << 1), l, ((l + r) >> 1), L, R));
  if (((l + r) >> 1) < R)
    ret = max(ret, Query(((u << 1) | 1), ((l + r) >> 1) + 1, r, L, R));
  return ret;
}
inline void Update(int p) {
  b[p].v = min(0ll, b[p].m - b[p].l) + min(0ll, b[p].m - b[p].r);
  Modify(1, 1, n, p, b[p].v);
}
int main() {
  read(n);
  for (int i = 1; i <= n; i++) read(a[i]), b[i].m = a[i];
  for (int i = 1; i < n; i++)
    c[i] = a[i] - a[i + 1], ans += abs(a[i] - a[i + 1]);
  for (int i = 1; i < n; i++)
    b[i].v += min(0ll, a[i] - a[i + 1]), b[i].r = a[i + 1];
  for (int i = 2; i <= n; i++)
    b[i].v += min(0ll, a[i] - a[i - 1]), b[i].l = a[i - 1];
  Build(1, 1, n);
  read(m);
  for (int i = 1; i <= m; i++) {
    long long Ans = 0, res = 0, ret = 0;
    int type, l, r;
    long long x;
    read(type);
    read(l);
    read(r);
    read(x);
    if (type == 1) {
      if (l == 1) {
        res = max(res, abs(c[1] + x));
        l = 2;
      }
      if (r == n) {
        res = max(res, abs(c[n - 1] - x));
        r = n - 1;
      }
      if (l == r) {
        ret =
            ans - abs(c[l - 1]) + abs(c[l - 1] - x) - abs(c[l]) + abs(c[l] + x);
      } else if (l <= r) {
        ret = ans + max(0ll, 2 * Query(1, 1, n, l, r) + 2 * x);
      }
      Ans = max(ret, res);
      printf("%I64d\n", Ans);
    } else {
      ans = ans - abs(c[l - 1]) + abs(c[l - 1] - x);
      c[l - 1] -= x;
      if (l - 1 >= 0) {
        b[l - 1].r += x;
        Update(l - 1);
        b[l].l -= x;
        Update(l);
      }
      ans = ans - abs(c[r]) + abs(c[r] + x);
      c[r] += x;
      if (r + 1 <= n) {
        b[r].r -= x;
        Update(r);
        b[r + 1].l += x;
        Update(r + 1);
      }
    }
  }
  return 0;
}

```