#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
void ckmin(T &a, U b) {
  if (a > b) a = b;
}
template <class T, class U>
void ckmax(T &a, U b) {
  if (a < b) a = b;
}
const int INF = 1000000007;
const int MAXN = 100013;
int N, Q;
long long arr[MAXN];
long long sum = 0;
long long ans = 0;
array<long long, 3> seg[3 * MAXN];
void build(int w, int L, int R) {
  if (L == R) {
    long long x = arr[L], y = -arr[L + 1];
    if (x > y) swap(x, y);
    seg[w][0] = -x - abs(x) - y - abs(y);
    seg[w][1] = -x - abs(x) + y - abs(y);
    seg[w][2] = x - abs(x) + y - abs(y);
    return;
  }
  int mid = (L + R) >> 1;
  build(w << 1, L, mid);
  build(w << 1 | 1, mid + 1, R);
  for (auto i = (0); i < (3); i++)
    seg[w][i] = max(seg[w << 1][i], seg[w << 1 | 1][i]);
}
void update(int w, int L, int R, int a) {
  if (L == R) {
    long long x = arr[L], y = -arr[L + 1];
    if (x > y) swap(x, y);
    seg[w][0] = -x - abs(x) - y - abs(y);
    seg[w][1] = -x - abs(x) + y - abs(y);
    seg[w][2] = x - abs(x) + y - abs(y);
    return;
  }
  int mid = (L + R) >> 1;
  if (a <= mid) update(w << 1, L, mid, a);
  if (mid < a) update(w << 1 | 1, mid + 1, R, a);
  for (auto i = (0); i < (3); i++)
    seg[w][i] = max(seg[w << 1][i], seg[w << 1 | 1][i]);
}
array<long long, 3> query(int w, int L, int R, int a, int b) {
  if (a <= L && R <= b) {
    return seg[w];
  }
  int mid = (L + R) >> 1;
  if (b <= mid) return query(w << 1, L, mid, a, b);
  if (mid < a) return query(w << 1 | 1, mid + 1, R, a, b);
  array<long long, 3> lt = query(w << 1, L, mid, a, b),
                      rt = query(w << 1 | 1, mid + 1, R, a, b);
  for (auto i = (0); i < (3); i++) ckmax(lt[i], rt[i]);
  return lt;
}
void incr(int idx, long long val) {
  sum -= abs(arr[idx]);
  arr[idx] += val;
  sum += abs(arr[idx]);
  if (idx != 0) update(1, 0, N - 2, idx - 1);
  if (idx != N - 1) update(1, 0, N - 2, idx);
}
int32_t main() {
  cout << fixed << setprecision(12);
  cerr << fixed << setprecision(4);
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> N;
  for (auto i = (0); i < (N); i++) {
    cin >> arr[i];
  }
  N--;
  for (auto i = (0); i < (N); i++) {
    arr[i] = arr[i + 1] - arr[i];
    sum += abs(arr[i]);
  }
  build(1, 0, N - 2);
  cin >> Q;
  while (Q--) {
    int qid, l, r;
    long long v;
    cin >> qid >> l >> r >> v;
    l--;
    r--;
    if (qid == 2) {
      incr(l - 1, v);
      incr(r, -v);
    } else {
      ans = -2 * INF;
      array<long long, 3> rec = query(1, 0, N - 2, l - 1, r - 1);
      ans = max(rec[1], max(rec[0] - 2 * v, rec[2] + 2 * v));
      ans += sum;
      cout << ans << '\n';
    }
  }
  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;
template <class T, class U>
void ckmin(T &a, U b) {
  if (a > b) a = b;
}
template <class T, class U>
void ckmax(T &a, U b) {
  if (a < b) a = b;
}
const int INF = 1000000007;
const int MAXN = 100013;
int N, Q;
long long arr[MAXN];
long long sum = 0;
long long ans = 0;
array<long long, 3> seg[3 * MAXN];
void build(int w, int L, int R) {
  if (L == R) {
    long long x = arr[L], y = -arr[L + 1];
    if (x > y) swap(x, y);
    seg[w][0] = -x - abs(x) - y - abs(y);
    seg[w][1] = -x - abs(x) + y - abs(y);
    seg[w][2] = x - abs(x) + y - abs(y);
    return;
  }
  int mid = (L + R) >> 1;
  build(w << 1, L, mid);
  build(w << 1 | 1, mid + 1, R);
  for (auto i = (0); i < (3); i++)
    seg[w][i] = max(seg[w << 1][i], seg[w << 1 | 1][i]);
}
void update(int w, int L, int R, int a) {
  if (L == R) {
    long long x = arr[L], y = -arr[L + 1];
    if (x > y) swap(x, y);
    seg[w][0] = -x - abs(x) - y - abs(y);
    seg[w][1] = -x - abs(x) + y - abs(y);
    seg[w][2] = x - abs(x) + y - abs(y);
    return;
  }
  int mid = (L + R) >> 1;
  if (a <= mid) update(w << 1, L, mid, a);
  if (mid < a) update(w << 1 | 1, mid + 1, R, a);
  for (auto i = (0); i < (3); i++)
    seg[w][i] = max(seg[w << 1][i], seg[w << 1 | 1][i]);
}
array<long long, 3> query(int w, int L, int R, int a, int b) {
  if (a <= L && R <= b) {
    return seg[w];
  }
  int mid = (L + R) >> 1;
  if (b <= mid) return query(w << 1, L, mid, a, b);
  if (mid < a) return query(w << 1 | 1, mid + 1, R, a, b);
  array<long long, 3> lt = query(w << 1, L, mid, a, b),
                      rt = query(w << 1 | 1, mid + 1, R, a, b);
  for (auto i = (0); i < (3); i++) ckmax(lt[i], rt[i]);
  return lt;
}
void incr(int idx, long long val) {
  sum -= abs(arr[idx]);
  arr[idx] += val;
  sum += abs(arr[idx]);
  if (idx != 0) update(1, 0, N - 2, idx - 1);
  if (idx != N - 1) update(1, 0, N - 2, idx);
}
int32_t main() {
  cout << fixed << setprecision(12);
  cerr << fixed << setprecision(4);
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> N;
  for (auto i = (0); i < (N); i++) {
    cin >> arr[i];
  }
  N--;
  for (auto i = (0); i < (N); i++) {
    arr[i] = arr[i + 1] - arr[i];
    sum += abs(arr[i]);
  }
  build(1, 0, N - 2);
  cin >> Q;
  while (Q--) {
    int qid, l, r;
    long long v;
    cin >> qid >> l >> r >> v;
    l--;
    r--;
    if (qid == 2) {
      incr(l - 1, v);
      incr(r, -v);
    } else {
      ans = -2 * INF;
      array<long long, 3> rec = query(1, 0, N - 2, l - 1, r - 1);
      ans = max(rec[1], max(rec[0] - 2 * v, rec[2] + 2 * v));
      ans += sum;
      cout << ans << '\n';
    }
  }
  return 0;
}

```