#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
const long long INF = ~0ULL >> 2;
struct SegmentTree {
  long long w[N << 2];
  int L, R, P;
  long long V;
  SegmentTree() { fill(w, w + (N << 2), INF); }
  void insert(int pos, long long value) {
    P = pos, V = value;
    ins(1, 1, N);
  }
  void remove(int pos) {
    P = pos;
    rm(1, 1, N);
  }
  long long query_min(int lt, int rt) {
    L = lt, R = rt;
    return qr(1, 1, N);
  }
  void ins(int o, int l, int r) {
    if (l == r) {
      w[o] = V;
    } else {
      int m = (l + r) >> 1;
      if (P <= m)
        ins(o << 1, l, m);
      else
        ins(o << 1 | 1, m + 1, r);
      w[o] = min(w[o << 1], w[o << 1 | 1]);
    }
  }
  void rm(int o, int l, int r) {
    if (l == r) {
      w[o] = INF;
    } else {
      int m = (l + r) >> 1;
      if (P <= m)
        rm(o << 1, l, m);
      else
        rm(o << 1 | 1, m + 1, r);
      w[o] = min(w[o << 1], w[o << 1 | 1]);
    }
  }
  long long qr(int o, int l, int r) {
    if (L <= l && r <= R) return w[o];
    int m = (l + r) >> 1;
    long long ans = INF;
    if (L <= m) ans = min(ans, qr(o << 1, l, m));
    if (R > m) ans = min(ans, qr(o << 1 | 1, m + 1, r));
    return ans;
  }
} t1, t4;
map<int, pair<long long, long long>> t2;
set<int> t3;
int n, q;
long long a[N], ans;
int add(int i) {
  if (i <= 1 || i >= n) return 0;
  if (a[i] >= 0 && a[i + 1] <= 0)
    t3.insert(i);
  else if (a[i] <= 0 && a[i + 1] <= 0)
    t1.insert(i, -a[i]);
  else if (a[i] >= 0 && a[i + 1] >= 0)
    t4.insert(i, a[i + 1]);
  else
    t2[i] = make_pair(-a[i], a[i + 1]);
  return 0;
}
int erase(int i) {
  if (i <= 1 || i >= n) return 0;
  if (a[i] >= 0 && a[i + 1] <= 0)
    t3.erase(i);
  else if (a[i] <= 0 && a[i + 1] <= 0)
    t1.remove(i);
  else if (a[i] >= 0 && a[i + 1] >= 0)
    t4.remove(i);
  else
    t2.erase(i);
  return 0;
}
int t, l, r, x;
long long gao() {
  long long x = ::x;
  auto it = t3.lower_bound(l);
  if (it != t3.end() && *it <= r) return 2 * x;
  long long ret = -INF;
  long long o = min(t1.query_min(l, r), t4.query_min(l, r));
  if (o != INF) ret = max(ret, x <= o ? 0 : 2 * (x - o));
  if (l == 1) ret = max(ret, abs(a[2] - x) - abs(a[2]));
  if (r == n) ret = max(ret, abs(a[n] + x) - abs(a[n]));
  auto iter = t2.lower_bound(l);
  if (iter != t2.end() && iter->first <= r) {
    long long p, q;
    tie(p, q) = iter->second;
    if (p > q) swap(p, q);
    if (x <= p)
      ret = max(ret, -2 * x);
    else if (x <= q)
      ret = max(ret, -2 * p);
    else
      ret = max(ret, 2 * (x - q - p));
  }
  return ret;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
  for (int i = n; i >= 2; --i) ans += abs(a[i] -= a[i - 1]);
  a[1] = 0;
  for (int i = 2; i < n; ++i) add(i);
  scanf("%d", &q);
  for (int i = 1; i <= q; ++i) {
    scanf("%d%d%d%d", &t, &l, &r, &x);
    if (t == 1) {
      printf("%lld\n", ans + gao());
    } else {
      ans -= abs(a[l]) + abs(a[r + 1]);
      for (int d = 0; d <= 1; ++d) erase(l - d), erase(r + d);
      if (l > 1) a[l] += x;
      if (r < n) a[r + 1] -= x;
      for (int d = 0; d <= 1; ++d) add(l - d), add(r + d);
      ans += abs(a[l]) + abs(a[r + 1]);
    }
  }
  return 0;
}

### Prompt

Your task is to create 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 N = 100100;
const long long INF = ~0ULL >> 2;
struct SegmentTree {
  long long w[N << 2];
  int L, R, P;
  long long V;
  SegmentTree() { fill(w, w + (N << 2), INF); }
  void insert(int pos, long long value) {
    P = pos, V = value;
    ins(1, 1, N);
  }
  void remove(int pos) {
    P = pos;
    rm(1, 1, N);
  }
  long long query_min(int lt, int rt) {
    L = lt, R = rt;
    return qr(1, 1, N);
  }
  void ins(int o, int l, int r) {
    if (l == r) {
      w[o] = V;
    } else {
      int m = (l + r) >> 1;
      if (P <= m)
        ins(o << 1, l, m);
      else
        ins(o << 1 | 1, m + 1, r);
      w[o] = min(w[o << 1], w[o << 1 | 1]);
    }
  }
  void rm(int o, int l, int r) {
    if (l == r) {
      w[o] = INF;
    } else {
      int m = (l + r) >> 1;
      if (P <= m)
        rm(o << 1, l, m);
      else
        rm(o << 1 | 1, m + 1, r);
      w[o] = min(w[o << 1], w[o << 1 | 1]);
    }
  }
  long long qr(int o, int l, int r) {
    if (L <= l && r <= R) return w[o];
    int m = (l + r) >> 1;
    long long ans = INF;
    if (L <= m) ans = min(ans, qr(o << 1, l, m));
    if (R > m) ans = min(ans, qr(o << 1 | 1, m + 1, r));
    return ans;
  }
} t1, t4;
map<int, pair<long long, long long>> t2;
set<int> t3;
int n, q;
long long a[N], ans;
int add(int i) {
  if (i <= 1 || i >= n) return 0;
  if (a[i] >= 0 && a[i + 1] <= 0)
    t3.insert(i);
  else if (a[i] <= 0 && a[i + 1] <= 0)
    t1.insert(i, -a[i]);
  else if (a[i] >= 0 && a[i + 1] >= 0)
    t4.insert(i, a[i + 1]);
  else
    t2[i] = make_pair(-a[i], a[i + 1]);
  return 0;
}
int erase(int i) {
  if (i <= 1 || i >= n) return 0;
  if (a[i] >= 0 && a[i + 1] <= 0)
    t3.erase(i);
  else if (a[i] <= 0 && a[i + 1] <= 0)
    t1.remove(i);
  else if (a[i] >= 0 && a[i + 1] >= 0)
    t4.remove(i);
  else
    t2.erase(i);
  return 0;
}
int t, l, r, x;
long long gao() {
  long long x = ::x;
  auto it = t3.lower_bound(l);
  if (it != t3.end() && *it <= r) return 2 * x;
  long long ret = -INF;
  long long o = min(t1.query_min(l, r), t4.query_min(l, r));
  if (o != INF) ret = max(ret, x <= o ? 0 : 2 * (x - o));
  if (l == 1) ret = max(ret, abs(a[2] - x) - abs(a[2]));
  if (r == n) ret = max(ret, abs(a[n] + x) - abs(a[n]));
  auto iter = t2.lower_bound(l);
  if (iter != t2.end() && iter->first <= r) {
    long long p, q;
    tie(p, q) = iter->second;
    if (p > q) swap(p, q);
    if (x <= p)
      ret = max(ret, -2 * x);
    else if (x <= q)
      ret = max(ret, -2 * p);
    else
      ret = max(ret, 2 * (x - q - p));
  }
  return ret;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
  for (int i = n; i >= 2; --i) ans += abs(a[i] -= a[i - 1]);
  a[1] = 0;
  for (int i = 2; i < n; ++i) add(i);
  scanf("%d", &q);
  for (int i = 1; i <= q; ++i) {
    scanf("%d%d%d%d", &t, &l, &r, &x);
    if (t == 1) {
      printf("%lld\n", ans + gao());
    } else {
      ans -= abs(a[l]) + abs(a[r + 1]);
      for (int d = 0; d <= 1; ++d) erase(l - d), erase(r + d);
      if (l > 1) a[l] += x;
      if (r < n) a[r + 1] -= x;
      for (int d = 0; d <= 1; ++d) add(l - d), add(r + d);
      ans += abs(a[l]) + abs(a[r + 1]);
    }
  }
  return 0;
}

```