#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, q;
long long tot, MXL = 1e18, F[N], MN[N * 2];
set<int> G, B;
inline void Add(int i, long long val) {
  for (; i < N; i += i & -i) F[i] += val;
}
inline long long Getval(int i) {
  long long rt = 0;
  for (; i; i -= i & -i) rt += F[i];
  return (rt);
}
inline void Set(int i, long long val) {
  for (MN[i += n] = val; i; i >>= 1) MN[i >> 1] = min(MN[i], MN[i ^ 1]);
}
inline long long GetMin(int l, int r) {
  long long Mn = MXL;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) Mn = min(Mn, MN[l++]);
    if (r & 1) Mn = min(Mn, MN[--r]);
  }
  return (Mn);
}
inline void Reset(int i) {
  if (i <= 1 || i >= n) return;
  G.erase(i);
  B.erase(i);
  long long a = Getval(i), b = Getval(i - 1), c = Getval(i + 1);
  if (a >= b && a >= c)
    G.insert(i), Set(i, MXL);
  else if (a < b && a < c)
    B.insert(i), Set(i, MXL);
  else
    Set(i, max(b, c) - a);
}
int main() {
  scanf("%d", &n);
  for (int i = 1, val; i <= n; i++)
    scanf("%d", &val), Add(i, val), Add(i + 1, -val);
  memset(MN, 63, sizeof(MN));
  for (int i = 2; i <= n; i++) tot += abs(Getval(i) - Getval(i - 1));
  for (int i = 1; i <= n; i++) Reset(i);
  scanf("%d", &q);
  for (; q; q--) {
    int t, l, r;
    long long x;
    scanf("%d%d%d%lld", &t, &l, &r, &x);
    r++;
    if (t == 2) {
      if (l > 1) tot -= abs(Getval(l) - Getval(l - 1));
      if (r <= n) tot -= abs(Getval(r) - Getval(r - 1));
      Add(l, x);
      Add(r, -x);
      Reset(l - 1);
      Reset(l);
      Reset(r - 1);
      Reset(r);
      if (l > 1) tot += abs(Getval(l) - Getval(l - 1));
      if (r <= n) tot += abs(Getval(r) - Getval(r - 1));
      continue;
    }
    auto it = G.lower_bound(l);
    if (it != G.end() && (*it) < r) {
      printf("%lld\n", tot + x + x);
      continue;
    }
    long long Mx = (x - GetMin(l, r)) * 2;
    if (GetMin(l, r) != MXL) Mx = max(Mx, 0ll);
    it = B.lower_bound(l);
    if (it != B.end() && (*it) < r) {
      long long a = Getval(*it), b = Getval((*it) - 1), c = Getval((*it) + 1);
      Mx = max(Mx, max(x - max(c, b) + a, 0ll) * 2 - min(x, min(b, c) - a) * 2);
    }
    if (l == 1) Mx = max(Mx, x - max(Getval(2) - Getval(1), 0ll) * 2);
    if (r == n + 1) Mx = max(Mx, x - max(Getval(n - 1) - Getval(n), 0ll) * 2);
    printf("%lld\n", tot + Mx);
  }
  return (0);
}

### Prompt

Please formulate 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 = 100005;
int n, q;
long long tot, MXL = 1e18, F[N], MN[N * 2];
set<int> G, B;
inline void Add(int i, long long val) {
  for (; i < N; i += i & -i) F[i] += val;
}
inline long long Getval(int i) {
  long long rt = 0;
  for (; i; i -= i & -i) rt += F[i];
  return (rt);
}
inline void Set(int i, long long val) {
  for (MN[i += n] = val; i; i >>= 1) MN[i >> 1] = min(MN[i], MN[i ^ 1]);
}
inline long long GetMin(int l, int r) {
  long long Mn = MXL;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) Mn = min(Mn, MN[l++]);
    if (r & 1) Mn = min(Mn, MN[--r]);
  }
  return (Mn);
}
inline void Reset(int i) {
  if (i <= 1 || i >= n) return;
  G.erase(i);
  B.erase(i);
  long long a = Getval(i), b = Getval(i - 1), c = Getval(i + 1);
  if (a >= b && a >= c)
    G.insert(i), Set(i, MXL);
  else if (a < b && a < c)
    B.insert(i), Set(i, MXL);
  else
    Set(i, max(b, c) - a);
}
int main() {
  scanf("%d", &n);
  for (int i = 1, val; i <= n; i++)
    scanf("%d", &val), Add(i, val), Add(i + 1, -val);
  memset(MN, 63, sizeof(MN));
  for (int i = 2; i <= n; i++) tot += abs(Getval(i) - Getval(i - 1));
  for (int i = 1; i <= n; i++) Reset(i);
  scanf("%d", &q);
  for (; q; q--) {
    int t, l, r;
    long long x;
    scanf("%d%d%d%lld", &t, &l, &r, &x);
    r++;
    if (t == 2) {
      if (l > 1) tot -= abs(Getval(l) - Getval(l - 1));
      if (r <= n) tot -= abs(Getval(r) - Getval(r - 1));
      Add(l, x);
      Add(r, -x);
      Reset(l - 1);
      Reset(l);
      Reset(r - 1);
      Reset(r);
      if (l > 1) tot += abs(Getval(l) - Getval(l - 1));
      if (r <= n) tot += abs(Getval(r) - Getval(r - 1));
      continue;
    }
    auto it = G.lower_bound(l);
    if (it != G.end() && (*it) < r) {
      printf("%lld\n", tot + x + x);
      continue;
    }
    long long Mx = (x - GetMin(l, r)) * 2;
    if (GetMin(l, r) != MXL) Mx = max(Mx, 0ll);
    it = B.lower_bound(l);
    if (it != B.end() && (*it) < r) {
      long long a = Getval(*it), b = Getval((*it) - 1), c = Getval((*it) + 1);
      Mx = max(Mx, max(x - max(c, b) + a, 0ll) * 2 - min(x, min(b, c) - a) * 2);
    }
    if (l == 1) Mx = max(Mx, x - max(Getval(2) - Getval(1), 0ll) * 2);
    if (r == n + 1) Mx = max(Mx, x - max(Getval(n - 1) - Getval(n), 0ll) * 2);
    printf("%lld\n", tot + Mx);
  }
  return (0);
}

```