#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const long long INF = 1e17 + 4;
int n, q;
long long a[MAXN], seg[MAXN * 4], finans;
long long get(int l, int r, int b = 1, int e = n - 1, int id = 1) {
  if (e <= l || r <= b) return INF;
  if (l <= b && e <= r) {
    return seg[id];
  }
  int mid = (b + e) / 2;
  return min(get(l, r, b, mid, id * 2), get(l, r, mid, e, id * 2 + 1));
}
void add(int ind, long long val, int b = 1, int e = n - 1, int id = 1) {
  if (ind < b || ind >= e) return;
  if (e - 1 == b) {
    seg[id] = val;
    return;
  }
  int mid = (b + e) / 2;
  add(ind, val, b, mid, id * 2), add(ind, val, mid, e, id * 2 + 1);
  seg[id] = min(seg[id * 2], seg[id * 2 + 1]);
}
void add_rule(int ind) {
  if (ind && ind < n - 1) add(ind, max(-a[ind], 0LL) + max(0LL, a[ind + 1]));
  return;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = n - 1; i >= 1; i--) a[i] = a[i] - a[i - 1], finans += abs(a[i]);
  for (int i = 0; i < n; i++) add_rule(i);
  cin >> q;
  while (q) {
    q--;
    int t, l, r;
    long long x;
    cin >> t >> l >> r >> x, l--, t--;
    if (t) {
      if (l) finans -= abs(a[l]), a[l] += x, finans += abs(a[l]);
      if (r < n) finans -= abs(a[r]), a[r] -= x, finans += abs(a[r]);
      add_rule(l), add_rule(l - 1), add_rule(r), add_rule(r - 1);
    } else {
      long long xx = finans;
      if (l) xx += abs(a[l] + x) - abs(a[l]);
      if (l < n - 1) xx += abs(a[l + 1] - x) - abs(a[l + 1]);
      if (l + 1 == r)
        cout << xx << endl;
      else {
        long long y = finans;
        if (r - 1) y += abs(a[r - 1] + x) - abs(a[r - 1]);
        if (r - 1 < n - 1) y += abs(a[r] - x) - abs(a[r]);
        l++, r--;
        xx = max(xx, y);
        if (l < r) {
          long long z = get(l, r);
          z = min(z, x);
          xx = max(finans + 2 * x - 2 * z, xx);
        }
        cout << xx << endl;
      }
    }
  }
  return 0;
}

### Prompt

Create a solution in Cpp for 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 MAXN = 1e5 + 10;
const long long INF = 1e17 + 4;
int n, q;
long long a[MAXN], seg[MAXN * 4], finans;
long long get(int l, int r, int b = 1, int e = n - 1, int id = 1) {
  if (e <= l || r <= b) return INF;
  if (l <= b && e <= r) {
    return seg[id];
  }
  int mid = (b + e) / 2;
  return min(get(l, r, b, mid, id * 2), get(l, r, mid, e, id * 2 + 1));
}
void add(int ind, long long val, int b = 1, int e = n - 1, int id = 1) {
  if (ind < b || ind >= e) return;
  if (e - 1 == b) {
    seg[id] = val;
    return;
  }
  int mid = (b + e) / 2;
  add(ind, val, b, mid, id * 2), add(ind, val, mid, e, id * 2 + 1);
  seg[id] = min(seg[id * 2], seg[id * 2 + 1]);
}
void add_rule(int ind) {
  if (ind && ind < n - 1) add(ind, max(-a[ind], 0LL) + max(0LL, a[ind + 1]));
  return;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = n - 1; i >= 1; i--) a[i] = a[i] - a[i - 1], finans += abs(a[i]);
  for (int i = 0; i < n; i++) add_rule(i);
  cin >> q;
  while (q) {
    q--;
    int t, l, r;
    long long x;
    cin >> t >> l >> r >> x, l--, t--;
    if (t) {
      if (l) finans -= abs(a[l]), a[l] += x, finans += abs(a[l]);
      if (r < n) finans -= abs(a[r]), a[r] -= x, finans += abs(a[r]);
      add_rule(l), add_rule(l - 1), add_rule(r), add_rule(r - 1);
    } else {
      long long xx = finans;
      if (l) xx += abs(a[l] + x) - abs(a[l]);
      if (l < n - 1) xx += abs(a[l + 1] - x) - abs(a[l + 1]);
      if (l + 1 == r)
        cout << xx << endl;
      else {
        long long y = finans;
        if (r - 1) y += abs(a[r - 1] + x) - abs(a[r - 1]);
        if (r - 1 < n - 1) y += abs(a[r] - x) - abs(a[r]);
        l++, r--;
        xx = max(xx, y);
        if (l < r) {
          long long z = get(l, r);
          z = min(z, x);
          xx = max(finans + 2 * x - 2 * z, xx);
        }
        cout << xx << endl;
      }
    }
  }
  return 0;
}

```