#include <bits/stdc++.h>
using namespace std;
vector<long long int> diff;
struct iii {
  long long int d, e, f;
};
iii comb(iii const& a, iii const& b) {
  return {max(a.d, b.d), max(a.e, b.e), max(a.f, b.f)};
}
vector<iii> st;
void build(int idx, int l, int r) {
  if (l + 1 == r) {
    long long int d1 = -diff[l - 1], d2 = diff[l], t = abs(d1) + abs(d2);
    st[idx] = {d1 + d2 - t, max(d1, d2) - min(d1, d2) - t, -d1 - d2 - t};
    return;
  }
  int m = l + (r - l) / 2;
  build(2 * idx + 1, l, m);
  build(2 * idx + 2, m, r);
  st[idx] = comb(st[2 * idx + 1], st[2 * idx + 2]);
}
iii query(int idx, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) return st[idx];
  if (r <= ql || qr <= l) return {LLONG_MIN, LLONG_MIN, LLONG_MIN};
  int m = l + (r - l) / 2;
  iii lv = query(2 * idx + 1, l, m, ql, qr);
  iii rv = query(2 * idx + 2, m, r, ql, qr);
  return comb(lv, rv);
}
void update(int idx, int l, int r, int ui) {
  if (ui <= l && r <= ui + 1) {
    long long int d1 = -diff[l - 1], d2 = diff[l], t = abs(d1) + abs(d2);
    st[idx] = {d1 + d2 - t, max(d1, d2) - min(d1, d2) - t, -d1 - d2 - t};
    return;
  }
  if (r <= ui || ui < l) return;
  int m = l + (r - l) / 2;
  update(2 * idx + 1, l, m, ui);
  update(2 * idx + 2, m, r, ui);
  st[idx] = comb(st[2 * idx + 1], st[2 * idx + 2]);
}
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  int q;
  cin >> q;
  diff.assign(n - 1, 0);
  long long int sum = 0;
  for (int i = 0; i < n - 1; ++i)
    diff[i] = a[i + 1] - a[i], sum += abs(diff[i]);
  st.assign(4 * n, iii());
  build(0, 1, n - 1);
  while (q--) {
    int t, l, r;
    long long int x;
    cin >> t >> l >> r >> x;
    l--, r--;
    if (t == 1) {
      iii q = query(0, 1, n - 1, l, r + 1);
      long long int res = sum + max({-2 * x + q.d, q.e, 2 * x + q.f});
      cout << res << endl;
    } else {
      sum -= abs(diff[l - 1]), diff[l - 1] += x, sum += abs(diff[l - 1]);
      sum -= abs(diff[r]), diff[r] -= x, sum += abs(diff[r]);
      update(0, 1, n - 1, l - 1);
      update(0, 1, n - 1, l);
      update(0, 1, n - 1, r);
      update(0, 1, n - 1, r + 1);
    }
  }
}

### 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>
using namespace std;
vector<long long int> diff;
struct iii {
  long long int d, e, f;
};
iii comb(iii const& a, iii const& b) {
  return {max(a.d, b.d), max(a.e, b.e), max(a.f, b.f)};
}
vector<iii> st;
void build(int idx, int l, int r) {
  if (l + 1 == r) {
    long long int d1 = -diff[l - 1], d2 = diff[l], t = abs(d1) + abs(d2);
    st[idx] = {d1 + d2 - t, max(d1, d2) - min(d1, d2) - t, -d1 - d2 - t};
    return;
  }
  int m = l + (r - l) / 2;
  build(2 * idx + 1, l, m);
  build(2 * idx + 2, m, r);
  st[idx] = comb(st[2 * idx + 1], st[2 * idx + 2]);
}
iii query(int idx, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) return st[idx];
  if (r <= ql || qr <= l) return {LLONG_MIN, LLONG_MIN, LLONG_MIN};
  int m = l + (r - l) / 2;
  iii lv = query(2 * idx + 1, l, m, ql, qr);
  iii rv = query(2 * idx + 2, m, r, ql, qr);
  return comb(lv, rv);
}
void update(int idx, int l, int r, int ui) {
  if (ui <= l && r <= ui + 1) {
    long long int d1 = -diff[l - 1], d2 = diff[l], t = abs(d1) + abs(d2);
    st[idx] = {d1 + d2 - t, max(d1, d2) - min(d1, d2) - t, -d1 - d2 - t};
    return;
  }
  if (r <= ui || ui < l) return;
  int m = l + (r - l) / 2;
  update(2 * idx + 1, l, m, ui);
  update(2 * idx + 2, m, r, ui);
  st[idx] = comb(st[2 * idx + 1], st[2 * idx + 2]);
}
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  int q;
  cin >> q;
  diff.assign(n - 1, 0);
  long long int sum = 0;
  for (int i = 0; i < n - 1; ++i)
    diff[i] = a[i + 1] - a[i], sum += abs(diff[i]);
  st.assign(4 * n, iii());
  build(0, 1, n - 1);
  while (q--) {
    int t, l, r;
    long long int x;
    cin >> t >> l >> r >> x;
    l--, r--;
    if (t == 1) {
      iii q = query(0, 1, n - 1, l, r + 1);
      long long int res = sum + max({-2 * x + q.d, q.e, 2 * x + q.f});
      cout << res << endl;
    } else {
      sum -= abs(diff[l - 1]), diff[l - 1] += x, sum += abs(diff[l - 1]);
      sum -= abs(diff[r]), diff[r] -= x, sum += abs(diff[r]);
      update(0, 1, n - 1, l - 1);
      update(0, 1, n - 1, l);
      update(0, 1, n - 1, r);
      update(0, 1, n - 1, r + 1);
    }
  }
}

```