#include <bits/stdc++.h>
int rd() {
  int k = 0;
  char c = getchar();
  while (c > '9' || c < '0') c = getchar();
  while (c >= '0' && c <= '9') k = k * 10 + c - 48, c = getchar();
  return k;
}
const int N = 100001;
long long Abs(long long x) { return x < 0 ? -x : x; }
long long Max(long long x, long long y) { return x > y ? x : y; }
long long Min(long long x, long long y) { return x < y ? x : y; }
int n, m, o, l, r, x;
long long s, a[N], t[N << 2];
void Make(int x, int l, int r) {
  if (l == r) {
    if (l > 1) t[x] = Max(0, a[l]) + Max(0, -a[l - 1]);
    s += Abs(a[l]);
    return;
  }
  int p = (l + r) >> 1, ls = x << 1, rs = ls | 1;
  Make(ls, l, p), Make(rs, p + 1, r), t[x] = Min(t[ls], t[rs]);
}
void Update(int x, int l, int r, int w, int v) {
  if (l == r) {
    s += Abs(a[l] + v) - Abs(a[l]), a[l] += v;
    if (l > 1) t[x] = Max(0, a[l]) + Max(0, -a[l - 1]);
    if (v && w < n - 1) Update(1, 1, n - 1, w + 1, 0);
    return;
  }
  int p = (l + r) >> 1, ls = x << 1, rs = ls | 1;
  if (w <= p)
    Update(ls, l, p, w, v);
  else
    Update(rs, p + 1, r, w, v);
  t[x] = Min(t[ls], t[rs]);
}
long long Query(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) return t[x];
  long long s = 9e18;
  int p = (l + r) >> 1, ls = x << 1, rs = ls | 1;
  if (L <= p) s = Min(s, Query(ls, l, p, L, R));
  if (p < R) s = Min(s, Query(rs, p + 1, r, L, R));
  return s;
}
int main() {
  n = rd();
  for (int i = 1; i <= n; ++i) a[i] = rd();
  for (int i = 1; i <= n; ++i) a[i] = a[i + 1] - a[i];
  Make(1, 1, n - 1), m = rd();
  while (m--) {
    o = rd(), l = rd(), r = rd(), x = rd();
    if (o == 1) {
      if (l == r) {
        if (l == 1)
          printf("%lld\n", s - Abs(a[1]) + Abs(a[1] - x));
        else if (l == n)
          printf("%lld\n", s - Abs(a[n - 1]) + Abs(a[n - 1] + x));
        else
          printf("%lld\n", s - Abs(a[l - 1]) - Abs(a[l]) + Abs(a[l - 1] + x) +
                               Abs(a[l] - x));
      } else {
        long long tmp = (x - Query(1, 1, n - 1, l > 1 ? l : 2, r)) * 2;
        if (l == 1) tmp = Max(tmp, Abs(a[1] - x) + Abs(a[1]));
        if (r == n) tmp = Max(tmp, Abs(a[n - 1] + x) - Abs(a[n - 1]));
        printf("%lld\n", Max(tmp, 0) + s);
      }
    } else {
      if (l > 1) Update(1, 1, n - 1, l - 1, x);
      if (r < n) Update(1, 1, n - 1, r, -x);
    }
  }
  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>
int rd() {
  int k = 0;
  char c = getchar();
  while (c > '9' || c < '0') c = getchar();
  while (c >= '0' && c <= '9') k = k * 10 + c - 48, c = getchar();
  return k;
}
const int N = 100001;
long long Abs(long long x) { return x < 0 ? -x : x; }
long long Max(long long x, long long y) { return x > y ? x : y; }
long long Min(long long x, long long y) { return x < y ? x : y; }
int n, m, o, l, r, x;
long long s, a[N], t[N << 2];
void Make(int x, int l, int r) {
  if (l == r) {
    if (l > 1) t[x] = Max(0, a[l]) + Max(0, -a[l - 1]);
    s += Abs(a[l]);
    return;
  }
  int p = (l + r) >> 1, ls = x << 1, rs = ls | 1;
  Make(ls, l, p), Make(rs, p + 1, r), t[x] = Min(t[ls], t[rs]);
}
void Update(int x, int l, int r, int w, int v) {
  if (l == r) {
    s += Abs(a[l] + v) - Abs(a[l]), a[l] += v;
    if (l > 1) t[x] = Max(0, a[l]) + Max(0, -a[l - 1]);
    if (v && w < n - 1) Update(1, 1, n - 1, w + 1, 0);
    return;
  }
  int p = (l + r) >> 1, ls = x << 1, rs = ls | 1;
  if (w <= p)
    Update(ls, l, p, w, v);
  else
    Update(rs, p + 1, r, w, v);
  t[x] = Min(t[ls], t[rs]);
}
long long Query(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) return t[x];
  long long s = 9e18;
  int p = (l + r) >> 1, ls = x << 1, rs = ls | 1;
  if (L <= p) s = Min(s, Query(ls, l, p, L, R));
  if (p < R) s = Min(s, Query(rs, p + 1, r, L, R));
  return s;
}
int main() {
  n = rd();
  for (int i = 1; i <= n; ++i) a[i] = rd();
  for (int i = 1; i <= n; ++i) a[i] = a[i + 1] - a[i];
  Make(1, 1, n - 1), m = rd();
  while (m--) {
    o = rd(), l = rd(), r = rd(), x = rd();
    if (o == 1) {
      if (l == r) {
        if (l == 1)
          printf("%lld\n", s - Abs(a[1]) + Abs(a[1] - x));
        else if (l == n)
          printf("%lld\n", s - Abs(a[n - 1]) + Abs(a[n - 1] + x));
        else
          printf("%lld\n", s - Abs(a[l - 1]) - Abs(a[l]) + Abs(a[l - 1] + x) +
                               Abs(a[l] - x));
      } else {
        long long tmp = (x - Query(1, 1, n - 1, l > 1 ? l : 2, r)) * 2;
        if (l == 1) tmp = Max(tmp, Abs(a[1] - x) + Abs(a[1]));
        if (r == n) tmp = Max(tmp, Abs(a[n - 1] + x) - Abs(a[n - 1]));
        printf("%lld\n", Max(tmp, 0) + s);
      }
    } else {
      if (l > 1) Update(1, 1, n - 1, l - 1, x);
      if (r < n) Update(1, 1, n - 1, r, -x);
    }
  }
  return 0;
}

```