#include <bits/stdc++.h>
using namespace std;
inline int getint() {
  char ch = getchar();
  int res = 0, sign = 1;
  if (ch == '-') sign = -1;
  while (ch < '0' || '9' < ch) {
    ch = getchar();
    if (ch == '-') sign = -1;
  }
  while ('0' <= ch && ch <= '9') {
    res = res * 10 + ch - '0';
    ch = getchar();
  }
  return res * sign;
}
int n, q;
struct tree {
  int op, ed;
  long long minn;
} tr[400007];
long long a[100007];
int l, r, v, p, x;
long long ans = 0;
void build(int v, int l, int r) {
  tr[v].op = l;
  tr[v].ed = r;
  if (l == r) {
    ans += abs(a[l]);
    tr[v].minn = max(0ll, -a[l - 1]) + max(0ll, a[l]);
    return;
  }
  int mid = l + r >> 1;
  build((v << 1), l, mid);
  build((v << 1 | 1), mid + 1, r);
  tr[v].minn = min(tr[(v << 1)].minn, tr[(v << 1 | 1)].minn);
}
void update(int v, int pos, int x) {
  if (tr[v].op == tr[v].ed) {
    ans -= abs(a[tr[v].op]);
    a[tr[v].op] += x;
    ans += abs(a[tr[v].op]);
    if (pos > 1)
      tr[v].minn = max(0ll, -a[tr[v].op - 1]) + max(0ll, a[tr[v].ed]);
    if (x && pos < n - 1) update(1, pos + 1, 0);
    return;
  }
  int mid = tr[v].op + tr[v].ed >> 1;
  if (mid >= pos)
    update((v << 1), pos, x);
  else
    update((v << 1 | 1), pos, x);
  tr[v].minn = min(tr[(v << 1)].minn, tr[(v << 1 | 1)].minn);
  return;
}
long long query(int v, int l, int r) {
  if (r < tr[v].op || l > tr[v].ed) return 0x7f7f7f7f7f7f7f7f;
  if (l <= tr[v].op && tr[v].ed <= r) return tr[v].minn;
  long long as = query((v << 1), l, r);
  as = min(as, query((v << 1 | 1), l, r));
  return as;
}
int main() {
  n = getint();
  for (int i = 1; i <= n; i++) a[i] = getint();
  for (int i = 1; i <= n; i++) a[i] = a[i + 1] - a[i];
  build(1, 1, n - 1);
  q = getint();
  while (q--) {
    p = getint();
    l = getint();
    r = getint();
    x = getint();
    if (p == 1) {
      if (l == r) {
        if (l == 1) {
          printf("%lld\n", ans - abs(a[1]) + (a[1] - x));
          continue;
        }
        if (l == n) {
          printf("%lld\n", ans - abs(a[n - 1]) + abs(a[n - 1] + x));
          continue;
        }
        printf("%lld\n", ans - abs(a[l]) - abs(a[l - 1]) + abs(a[l - 1] + x) +
                             abs(a[l] - x));
      } else {
        long long del = 0;
        del = max(del, 2 * x - 2 * query(1, max(l, 2), r));
        if (l == 1) del = max(del, -abs(a[l]) + abs(a[l] - x));
        if (r == n) del = max(del, -abs(a[r - 1]) + abs(a[r - 1] + x));
        printf("%lld\n", ans + del);
      }
    } else {
      if (l > 1) update(1, l - 1, x);
      if (r < n) update(1, r, -x);
    }
  }
  return 0;
}

### 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;
inline int getint() {
  char ch = getchar();
  int res = 0, sign = 1;
  if (ch == '-') sign = -1;
  while (ch < '0' || '9' < ch) {
    ch = getchar();
    if (ch == '-') sign = -1;
  }
  while ('0' <= ch && ch <= '9') {
    res = res * 10 + ch - '0';
    ch = getchar();
  }
  return res * sign;
}
int n, q;
struct tree {
  int op, ed;
  long long minn;
} tr[400007];
long long a[100007];
int l, r, v, p, x;
long long ans = 0;
void build(int v, int l, int r) {
  tr[v].op = l;
  tr[v].ed = r;
  if (l == r) {
    ans += abs(a[l]);
    tr[v].minn = max(0ll, -a[l - 1]) + max(0ll, a[l]);
    return;
  }
  int mid = l + r >> 1;
  build((v << 1), l, mid);
  build((v << 1 | 1), mid + 1, r);
  tr[v].minn = min(tr[(v << 1)].minn, tr[(v << 1 | 1)].minn);
}
void update(int v, int pos, int x) {
  if (tr[v].op == tr[v].ed) {
    ans -= abs(a[tr[v].op]);
    a[tr[v].op] += x;
    ans += abs(a[tr[v].op]);
    if (pos > 1)
      tr[v].minn = max(0ll, -a[tr[v].op - 1]) + max(0ll, a[tr[v].ed]);
    if (x && pos < n - 1) update(1, pos + 1, 0);
    return;
  }
  int mid = tr[v].op + tr[v].ed >> 1;
  if (mid >= pos)
    update((v << 1), pos, x);
  else
    update((v << 1 | 1), pos, x);
  tr[v].minn = min(tr[(v << 1)].minn, tr[(v << 1 | 1)].minn);
  return;
}
long long query(int v, int l, int r) {
  if (r < tr[v].op || l > tr[v].ed) return 0x7f7f7f7f7f7f7f7f;
  if (l <= tr[v].op && tr[v].ed <= r) return tr[v].minn;
  long long as = query((v << 1), l, r);
  as = min(as, query((v << 1 | 1), l, r));
  return as;
}
int main() {
  n = getint();
  for (int i = 1; i <= n; i++) a[i] = getint();
  for (int i = 1; i <= n; i++) a[i] = a[i + 1] - a[i];
  build(1, 1, n - 1);
  q = getint();
  while (q--) {
    p = getint();
    l = getint();
    r = getint();
    x = getint();
    if (p == 1) {
      if (l == r) {
        if (l == 1) {
          printf("%lld\n", ans - abs(a[1]) + (a[1] - x));
          continue;
        }
        if (l == n) {
          printf("%lld\n", ans - abs(a[n - 1]) + abs(a[n - 1] + x));
          continue;
        }
        printf("%lld\n", ans - abs(a[l]) - abs(a[l - 1]) + abs(a[l - 1] + x) +
                             abs(a[l] - x));
      } else {
        long long del = 0;
        del = max(del, 2 * x - 2 * query(1, max(l, 2), r));
        if (l == 1) del = max(del, -abs(a[l]) + abs(a[l] - x));
        if (r == n) del = max(del, -abs(a[r - 1]) + abs(a[r - 1] + x));
        printf("%lld\n", ans + del);
      }
    } else {
      if (l > 1) update(1, l - 1, x);
      if (r < n) update(1, r, -x);
    }
  }
  return 0;
}

```