human
Can you provide a Python program to find the maximum possible value of f(A), if x is to be added to one element in the range [l, r] given the following:
CPP solution for "Fafa has an array A of n positive integers, the function f(A) is defined as . 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 . 

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":
assistant
#Here is Python program to find the maximum possible value of f(A), if x is to be added to one element in the range [l, r].
 #include <bits/stdc++.h>
using namespace std;
template <class V, int ME>
class BIT {
 public:
  V bit[1 << ME];
  V operator[](int e) {
    if (e < 0) return 0;
    V s = 0;
    e++;
    while (e) s += bit[e - 1], e -= e & -e;
    return s;
  }
  void add(int e, V v) {
    e++;
    while (e <= 1 << ME) bit[e - 1] += v, e += e & -e;
  }
};
BIT<signed long long, 20> bt;
template <class V, int NV>
class SegTree_1 {
 public:
  vector<V> val;
  static V const def = 1LL << 60;
  V comp(V l, V r) { return min(l, r); };
  SegTree_1() { val = vector<V>(NV * 2, 1LL << 60); };
  V getval(int x, int y, int l = 0, int r = NV, int k = 1) {
    if (r <= x || y <= l) return def;
    if (x <= l && r <= y) return val[k];
    return comp(getval(x, y, l, (l + r) / 2, k * 2),
                getval(x, y, (l + r) / 2, r, k * 2 + 1));
  }
  void update(int entry, V v) {
    entry += NV;
    val[entry] = v;
    while (entry > 1)
      entry >>= 1, val[entry] = comp(val[entry * 2], val[entry * 2 + 1]);
  }
};
int N, Q;
signed long long AS;
set<int> S, S2;
SegTree_1<signed long long, 1 << 20> penalty;
void update(int cur) {
  if (cur <= 1 || cur >= N) return;
  S.erase(cur);
  S2.erase(cur);
  penalty.update(cur, 1LL << 60);
  if (bt[cur] >= bt[cur - 1] && bt[cur] >= bt[cur + 1]) {
    penalty.update(cur, 0);
  } else if (bt[cur] <= bt[cur - 1] && bt[cur] <= bt[cur + 1]) {
    S2.insert(cur);
  } else {
    penalty.update(cur, max(bt[cur - 1] - bt[cur], bt[cur + 1] - bt[cur]));
  }
}
signed long long hoge(int cur, int add) {
  signed long long ret = 0;
  ret -= abs(bt[cur] - bt[cur - 1]);
  ret += abs(bt[cur] + add - bt[cur - 1]);
  ret -= abs(bt[cur] - bt[cur + 1]);
  ret += abs(bt[cur] + add - bt[cur + 1]);
  return ret;
}
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  scanf("%d", &N);
  int pre = 0;
  for (i = 1; i <= N; i++) {
    scanf("%d", &x);
    bt.add(i, x - pre);
    if (i > 1) AS += abs(x - pre);
    pre = x;
  }
  for (i = 2; i <= N - 1; i++) update(i);
  S.insert(N + 1);
  S2.insert(N + 1);
  S2.insert(N + 2);
...