#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18L;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
const int Mod = 1e9 + 7;
long long b[maxn];
int a[maxn], n, q;
int lowbit(int x) { return x & (-x); }
void add(int i, int x) {
  while (i <= n) {
    b[i] += x;
    i += lowbit(i);
  }
}
long long sum(int i) {
  long long ans = 0;
  while (i) {
    ans += b[i];
    i -= lowbit(i);
  }
  return ans;
}
bool down[maxn * 4];
long long v1[maxn * 4], v2[maxn * 4];
void push_up(int i) {
  v1[i] = max(v1[i << 1], v1[(i << 1) | 1]);
  down[i] = down[i << 1] | down[(i << 1) | 1];
}
void build_tree(int i, int L, int R) {
  if (L == R) {
    v1[i] = a[L] - a[L - 1];
    v2[i] = a[L] - a[L + 1];
    if (v1[i] > v2[i]) swap(v1[i], v2[i]);
    if (v2[i] < 0)
      down[i] = true;
    else
      down[i] = false;
    return;
  }
  int mid = (L + R) >> 1;
  build_tree(i << 1, L, mid);
  build_tree((i << 1) | 1, mid + 1, R);
  push_up(i);
}
long long exist(int i, int L, int R, int l, int r) {
  if (L == l && R == r) return v1[i];
  int mid = (L + R) >> 1;
  if (mid >= r)
    return exist(i << 1, L, mid, l, r);
  else if (mid < l)
    return exist((i << 1) | 1, mid + 1, R, l, r);
  return max((exist(i << 1, L, mid, l, mid)),
             exist((i << 1) | 1, mid + 1, R, mid + 1, r));
}
int get_pos(int i, int L, int R, int l, int r) {
  if (!down[i]) return -1;
  if (L == R) return L;
  int mid = (L + R) >> 1;
  if (mid >= r)
    return get_pos(i << 1, L, mid, l, r);
  else if (mid < l)
    return get_pos((i << 1) | 1, mid + 1, R, l, r);
  int x = get_pos(i << 1, L, mid, l, mid);
  if (x != -1) return x;
  return get_pos((i << 1) | 1, mid + 1, R, mid + 1, r);
}
void update(int i, int L, int R, int pos) {
  if (L == R) {
    long long x = sum(L);
    v1[i] = x - sum(L - 1);
    v2[i] = x - sum(L + 1);
    if (v1[i] > v2[i]) swap(v1[i], v2[i]);
    if (v2[i] < 0)
      down[i] = true;
    else
      down[i] = false;
    return;
  }
  int mid = (L + R) >> 1;
  if (mid >= pos)
    update(i << 1, L, mid, pos);
  else
    update((i << 1) | 1, mid + 1, R, pos);
  push_up(i);
}
long long cal(long long c, long long d, long long x) {
  if (c >= d)
    return x;
  else if (c + x <= d)
    return -x;
  return (c + x - d) - (d - c);
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  long long org = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    add(i, a[i]);
    add(i + 1, -a[i]);
    if (i > 1) org += abs(a[i] - a[i - 1]);
  }
  build_tree(1, 1, n);
  cin >> q;
  while (q--) {
    int op, l, r, x;
    cin >> op >> l >> r >> x;
    if (op == 1) {
      long long e1 = -INF, en = -INF, e = -INF;
      if (l == 1) {
        e1 = cal(sum(1), sum(2), x);
        l++;
      }
      if (r == n) {
        en = cal(sum(n), sum(n - 1), x);
        r--;
      }
      if (l <= r) {
        long long y = exist(1, 1, n, l, r);
        if (y >= 0)
          e = 2 * x;
        else {
          int pos = get_pos(1, 1, n, l, r);
          if (pos != -1) {
            long long val = sum(pos);
            e = cal(val, sum(pos - 1), x) + cal(val, sum(pos + 1), x);
            if (l <= pos - 1)
              e = max(e, cal(exist(1, 1, n, l, pos - 1), 0, x) + x);
            if (pos + 1 <= r)
              e = max(e, cal(exist(1, 1, n, pos + 1, r), 0, x) + x);
          } else
            e = cal(y, 0, x) + x;
        }
      }
      e = max(e, max(e1, en));
      cout << org + e << endl;
    } else {
      if (l > 1) org += cal(sum(l), sum(l - 1), x);
      if (r < n) org += cal(sum(r), sum(r + 1), x);
      add(l, x);
      add(r + 1, -x);
      if (l > 1) {
        update(1, 1, n, l - 1);
        update(1, 1, n, l);
      }
      if (r < n) {
        update(1, 1, n, r);
        update(1, 1, n, r + 1);
      }
    }
  }
  return 0;
}

### Prompt

Develop a solution in Cpp 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;
const long long INF = 1e18L;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
const int Mod = 1e9 + 7;
long long b[maxn];
int a[maxn], n, q;
int lowbit(int x) { return x & (-x); }
void add(int i, int x) {
  while (i <= n) {
    b[i] += x;
    i += lowbit(i);
  }
}
long long sum(int i) {
  long long ans = 0;
  while (i) {
    ans += b[i];
    i -= lowbit(i);
  }
  return ans;
}
bool down[maxn * 4];
long long v1[maxn * 4], v2[maxn * 4];
void push_up(int i) {
  v1[i] = max(v1[i << 1], v1[(i << 1) | 1]);
  down[i] = down[i << 1] | down[(i << 1) | 1];
}
void build_tree(int i, int L, int R) {
  if (L == R) {
    v1[i] = a[L] - a[L - 1];
    v2[i] = a[L] - a[L + 1];
    if (v1[i] > v2[i]) swap(v1[i], v2[i]);
    if (v2[i] < 0)
      down[i] = true;
    else
      down[i] = false;
    return;
  }
  int mid = (L + R) >> 1;
  build_tree(i << 1, L, mid);
  build_tree((i << 1) | 1, mid + 1, R);
  push_up(i);
}
long long exist(int i, int L, int R, int l, int r) {
  if (L == l && R == r) return v1[i];
  int mid = (L + R) >> 1;
  if (mid >= r)
    return exist(i << 1, L, mid, l, r);
  else if (mid < l)
    return exist((i << 1) | 1, mid + 1, R, l, r);
  return max((exist(i << 1, L, mid, l, mid)),
             exist((i << 1) | 1, mid + 1, R, mid + 1, r));
}
int get_pos(int i, int L, int R, int l, int r) {
  if (!down[i]) return -1;
  if (L == R) return L;
  int mid = (L + R) >> 1;
  if (mid >= r)
    return get_pos(i << 1, L, mid, l, r);
  else if (mid < l)
    return get_pos((i << 1) | 1, mid + 1, R, l, r);
  int x = get_pos(i << 1, L, mid, l, mid);
  if (x != -1) return x;
  return get_pos((i << 1) | 1, mid + 1, R, mid + 1, r);
}
void update(int i, int L, int R, int pos) {
  if (L == R) {
    long long x = sum(L);
    v1[i] = x - sum(L - 1);
    v2[i] = x - sum(L + 1);
    if (v1[i] > v2[i]) swap(v1[i], v2[i]);
    if (v2[i] < 0)
      down[i] = true;
    else
      down[i] = false;
    return;
  }
  int mid = (L + R) >> 1;
  if (mid >= pos)
    update(i << 1, L, mid, pos);
  else
    update((i << 1) | 1, mid + 1, R, pos);
  push_up(i);
}
long long cal(long long c, long long d, long long x) {
  if (c >= d)
    return x;
  else if (c + x <= d)
    return -x;
  return (c + x - d) - (d - c);
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  long long org = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    add(i, a[i]);
    add(i + 1, -a[i]);
    if (i > 1) org += abs(a[i] - a[i - 1]);
  }
  build_tree(1, 1, n);
  cin >> q;
  while (q--) {
    int op, l, r, x;
    cin >> op >> l >> r >> x;
    if (op == 1) {
      long long e1 = -INF, en = -INF, e = -INF;
      if (l == 1) {
        e1 = cal(sum(1), sum(2), x);
        l++;
      }
      if (r == n) {
        en = cal(sum(n), sum(n - 1), x);
        r--;
      }
      if (l <= r) {
        long long y = exist(1, 1, n, l, r);
        if (y >= 0)
          e = 2 * x;
        else {
          int pos = get_pos(1, 1, n, l, r);
          if (pos != -1) {
            long long val = sum(pos);
            e = cal(val, sum(pos - 1), x) + cal(val, sum(pos + 1), x);
            if (l <= pos - 1)
              e = max(e, cal(exist(1, 1, n, l, pos - 1), 0, x) + x);
            if (pos + 1 <= r)
              e = max(e, cal(exist(1, 1, n, pos + 1, r), 0, x) + x);
          } else
            e = cal(y, 0, x) + x;
        }
      }
      e = max(e, max(e1, en));
      cout << org + e << endl;
    } else {
      if (l > 1) org += cal(sum(l), sum(l - 1), x);
      if (r < n) org += cal(sum(r), sum(r + 1), x);
      add(l, x);
      add(r + 1, -x);
      if (l > 1) {
        update(1, 1, n, l - 1);
        update(1, 1, n, l);
      }
      if (r < n) {
        update(1, 1, n, r);
        update(1, 1, n, r + 1);
      }
    }
  }
  return 0;
}

```