#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, pos, q;
int a[maxn];
long long dlt[maxn], tr[maxn << 2];
void modify(int o, int l, int r) {
  if (l + 1 == r) {
    tr[o] = 0;
    if (dlt[pos - 1] > 0) {
      tr[o] += dlt[pos - 1];
    }
    if (dlt[pos] < 0) {
      tr[o] += -dlt[pos];
    }
    return;
  }
  int mid = (l + r) >> 1;
  if (pos < mid) {
    modify(((o) << 1), l, mid);
  } else {
    modify((((o) << 1) | 1), mid, r);
  }
  tr[o] = min(tr[((o) << 1)], tr[(((o) << 1) | 1)]);
}
long long query(int o, int l, int r, int ql, int qr) {
  if (l == ql && r == qr) {
    return tr[o];
  }
  int mid = (l + r) >> 1;
  if (ql < mid) {
    if (qr > mid) {
      return min(query(((o) << 1), l, mid, ql, mid),
                 query((((o) << 1) | 1), mid, r, mid, qr));
    } else {
      return query(((o) << 1), l, mid, ql, qr);
    }
  } else {
    return query((((o) << 1) | 1), mid, r, ql, qr);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int i, j, k, t, l, r, x;
  long long sum, adj;
  cin >> n;
  for (i = (1); i <= (n); i++) {
    cin >> a[i];
  }
  sum = 0;
  for (i = (1); i <= (n - 1); i++) {
    dlt[i] = a[i] - a[i + 1];
    sum += abs(dlt[i]);
    if (i > 1) {
      pos = i;
      modify(1, 2, n);
    }
  }
  cin >> q;
  for (; q--;) {
    cin >> t >> l >> r >> x;
    if (t == 1) {
      if (l == r) {
        cout << sum - abs(dlt[l - 1]) - abs(dlt[l]) + abs(dlt[l - 1] - x) +
                    abs(x + dlt[l])
             << endl;
        continue;
      }
      adj = query(1, 2, n, l, r + 1);
      if (adj >= x) {
        cout << sum << endl;
      } else {
        cout << sum + ((x - adj) << 1) << endl;
      }
    } else {
      sum -= abs(dlt[l - 1]) - abs(dlt[l - 1] - x);
      dlt[l - 1] -= x;
      pos = l;
      modify(1, 2, n);
      if (l > 2) {
        pos = l - 1;
        modify(1, 2, n);
      }
      sum -= abs(dlt[r]) - abs(x + dlt[r]);
      dlt[r] += x;
      pos = r;
      modify(1, 2, n);
      if (r < n - 1) {
        pos = r + 1;
        modify(1, 2, n);
      }
    }
  }
  return 0;
}

### Prompt

Please formulate 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 maxn = 1e5 + 10;
int n, pos, q;
int a[maxn];
long long dlt[maxn], tr[maxn << 2];
void modify(int o, int l, int r) {
  if (l + 1 == r) {
    tr[o] = 0;
    if (dlt[pos - 1] > 0) {
      tr[o] += dlt[pos - 1];
    }
    if (dlt[pos] < 0) {
      tr[o] += -dlt[pos];
    }
    return;
  }
  int mid = (l + r) >> 1;
  if (pos < mid) {
    modify(((o) << 1), l, mid);
  } else {
    modify((((o) << 1) | 1), mid, r);
  }
  tr[o] = min(tr[((o) << 1)], tr[(((o) << 1) | 1)]);
}
long long query(int o, int l, int r, int ql, int qr) {
  if (l == ql && r == qr) {
    return tr[o];
  }
  int mid = (l + r) >> 1;
  if (ql < mid) {
    if (qr > mid) {
      return min(query(((o) << 1), l, mid, ql, mid),
                 query((((o) << 1) | 1), mid, r, mid, qr));
    } else {
      return query(((o) << 1), l, mid, ql, qr);
    }
  } else {
    return query((((o) << 1) | 1), mid, r, ql, qr);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int i, j, k, t, l, r, x;
  long long sum, adj;
  cin >> n;
  for (i = (1); i <= (n); i++) {
    cin >> a[i];
  }
  sum = 0;
  for (i = (1); i <= (n - 1); i++) {
    dlt[i] = a[i] - a[i + 1];
    sum += abs(dlt[i]);
    if (i > 1) {
      pos = i;
      modify(1, 2, n);
    }
  }
  cin >> q;
  for (; q--;) {
    cin >> t >> l >> r >> x;
    if (t == 1) {
      if (l == r) {
        cout << sum - abs(dlt[l - 1]) - abs(dlt[l]) + abs(dlt[l - 1] - x) +
                    abs(x + dlt[l])
             << endl;
        continue;
      }
      adj = query(1, 2, n, l, r + 1);
      if (adj >= x) {
        cout << sum << endl;
      } else {
        cout << sum + ((x - adj) << 1) << endl;
      }
    } else {
      sum -= abs(dlt[l - 1]) - abs(dlt[l - 1] - x);
      dlt[l - 1] -= x;
      pos = l;
      modify(1, 2, n);
      if (l > 2) {
        pos = l - 1;
        modify(1, 2, n);
      }
      sum -= abs(dlt[r]) - abs(x + dlt[r]);
      dlt[r] += x;
      pos = r;
      modify(1, 2, n);
      if (r < n - 1) {
        pos = r + 1;
        modify(1, 2, n);
      }
    }
  }
  return 0;
}

```