#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
typedef long long node;
const long long neutro = 0;
struct RMQ_add {
  int sz;
  node t[4 * 200000];
  node &operator[](int p) { return t[sz + p]; }
  void init(int n) {
    sz = 1 << (32 - __builtin_clz(n));
    for (int i = (0); i < (int)(2 * sz); i++) t[i] = neutro;
  }
  void updall() {
    for (int i = ((int)sz) - 1; i >= 0; i--) {
      t[i] = (t[2 * i] + t[2 * i + 1]);
    }
  }
  node get(int i, int j) { return get(i, j, 1, 0, sz); }
  node get(int i, int j, int n, int a, int b) {
    if (j <= a || i >= b) return neutro;
    if (i <= a && b <= j) return t[n];
    int c = (a + b) / 2;
    return (get(i, j, 2 * n, a, c) + get(i, j, 2 * n + 1, c, b));
  }
  void set(int p, node val) {
    for (p += sz; p > 0 && t[p] != val;) {
      t[p] = val;
      p /= 2;
      val = (t[p * 2] + t[p * 2 + 1]);
    }
  }
} D, A, Z;
const long long neutro2 = INF;
struct RMQ_min {
  int sz;
  node t[4 * 200000];
  node &operator[](int p) { return t[sz + p]; }
  void init(int n) {
    sz = 1 << (32 - __builtin_clz(n));
    for (int i = (0); i < (int)(2 * sz); i++) t[i] = neutro2;
  }
  void updall() {
    for (int i = ((int)sz) - 1; i >= 0; i--) {
      t[i] = min(t[2 * i], t[2 * i + 1]);
    }
  }
  node get(int i, int j) { return get(i, j, 1, 0, sz); }
  node get(int i, int j, int n, int a, int b) {
    if (j <= a || i >= b) return neutro2;
    if (i <= a && b <= j) return t[n];
    int c = (a + b) / 2;
    return min(get(i, j, 2 * n, a, c), get(i, j, 2 * n + 1, c, b));
  }
  void set(int p, node val) {
    for (p += sz; p > 0 && t[p] != val;) {
      t[p] = val;
      p /= 2;
      val = min(t[p * 2], t[p * 2 + 1]);
    }
  }
} AC;
int n;
long long x;
vector<long long> Ini;
long long ans;
void KillMeSoftly(int l, int r) {
  if (r == l) return;
  long long val = AC.get(l, r), val2 = abs(val - x);
  ans = max(ans, A.get(0, n) + x - val + val2);
}
void YeaBoi() { ans = max(ans, A.get(0, n) + 2 * x); }
int find_z(int l, int r) {
  while (r - l > 1) {
    int m = (l + r) / 2;
    if (Z.get(l, m))
      r = m;
    else
      l = m;
  }
  return l;
}
void Cacona(int p) {
  long long val1 = D.get(p, p + 1), val2 = D.get(p + 1, p + 2);
  A.set(p, abs(val1 + x));
  A.set(p + 1, abs(val2 - x));
  ans = max(ans, A.get(0, n));
  A.set(p, abs(val1));
  A.set(p + 1, abs(val2));
}
int main() {
  while (scanf("%d", &n) == 1) {
    Ini.resize(n);
    for (int i = (0); i < (int)(n); i++) scanf("%lld", &Ini[i]);
    n--;
    D.init(n);
    A.init(n);
    Z.init(n);
    AC.init(n);
    for (int i = (0); i < (int)(n); i++) {
      D[i] = Ini[i + 1] - Ini[i];
      A[i] = AC[i] = abs(D[i]);
      Z[i] = (D[i] == 0);
    }
    D.updall();
    A.updall();
    Z.updall();
    AC.updall();
    int q;
    scanf("%d", &q);
    for (int cs = (0); cs < (int)(q); cs++) {
      int l, r, op;
      ans = -INF;
      scanf("%d %d %d %lld", &op, &l, &r, &x);
      l--;
      if (op == 1) {
        l--;
        int cntz = Z.get(l, r);
        switch (cntz) {
          case 0: {
            if ((A.get(l, r) == abs(D.get(l, r)))) {
              if (D[l] > 0)
                KillMeSoftly(l + 1, r);
              else
                KillMeSoftly(l, r - 1);
              break;
            }
            if (D[l] > 0) {
              YeaBoi();
              break;
            }
            int i = l + 1, d = r, m;
            while (d - i > 1) {
              m = (i + d) / 2;
              if ((A.get(l, m) == abs(D.get(l, m))))
                i = m;
              else
                d = m;
            }
            if ((A.get(i, r) == abs(D.get(i, r)))) {
              Cacona(i - 1);
              KillMeSoftly(l, i - 1);
              KillMeSoftly(i + 1, r);
            } else
              YeaBoi();
            break;
          }
          case 1: {
            int d = find_z(l, r);
            if (d > l &&
                ((D[d - 1] > 0) || (!(A.get(l, d) == abs(D.get(l, d)))))) {
              YeaBoi();
              break;
            }
            if (d < r - 1 && ((D[d + 1] < 0) ||
                              (!(A.get(d + 1, r) == abs(D.get(d + 1, r)))))) {
              YeaBoi();
              break;
            }
            KillMeSoftly(l, d);
            KillMeSoftly(d + 1, r);
            break;
          }
          default: {
            YeaBoi();
            break;
          }
        }
        printf("%lld\n", ans);
      } else {
        l--;
        r--;
        if (l >= 0) {
          long long val = D.get(l, l + 1) + x;
          D.set(l, val);
          A.set(l, abs(val));
          AC.set(l, abs(val));
          Z.set(l, (val == 0 ? 1 : 0));
        }
        if (r < n) {
          long long val = D.get(r, r + 1) - x;
          D.set(r, val);
          A.set(r, abs(val));
          AC.set(r, abs(val));
          Z.set(r, (val == 0 ? 1 : 0));
        }
      }
    }
  }
  return 0;
}

### Prompt

Create a solution in Cpp for 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 long long INF = 1e18;
typedef long long node;
const long long neutro = 0;
struct RMQ_add {
  int sz;
  node t[4 * 200000];
  node &operator[](int p) { return t[sz + p]; }
  void init(int n) {
    sz = 1 << (32 - __builtin_clz(n));
    for (int i = (0); i < (int)(2 * sz); i++) t[i] = neutro;
  }
  void updall() {
    for (int i = ((int)sz) - 1; i >= 0; i--) {
      t[i] = (t[2 * i] + t[2 * i + 1]);
    }
  }
  node get(int i, int j) { return get(i, j, 1, 0, sz); }
  node get(int i, int j, int n, int a, int b) {
    if (j <= a || i >= b) return neutro;
    if (i <= a && b <= j) return t[n];
    int c = (a + b) / 2;
    return (get(i, j, 2 * n, a, c) + get(i, j, 2 * n + 1, c, b));
  }
  void set(int p, node val) {
    for (p += sz; p > 0 && t[p] != val;) {
      t[p] = val;
      p /= 2;
      val = (t[p * 2] + t[p * 2 + 1]);
    }
  }
} D, A, Z;
const long long neutro2 = INF;
struct RMQ_min {
  int sz;
  node t[4 * 200000];
  node &operator[](int p) { return t[sz + p]; }
  void init(int n) {
    sz = 1 << (32 - __builtin_clz(n));
    for (int i = (0); i < (int)(2 * sz); i++) t[i] = neutro2;
  }
  void updall() {
    for (int i = ((int)sz) - 1; i >= 0; i--) {
      t[i] = min(t[2 * i], t[2 * i + 1]);
    }
  }
  node get(int i, int j) { return get(i, j, 1, 0, sz); }
  node get(int i, int j, int n, int a, int b) {
    if (j <= a || i >= b) return neutro2;
    if (i <= a && b <= j) return t[n];
    int c = (a + b) / 2;
    return min(get(i, j, 2 * n, a, c), get(i, j, 2 * n + 1, c, b));
  }
  void set(int p, node val) {
    for (p += sz; p > 0 && t[p] != val;) {
      t[p] = val;
      p /= 2;
      val = min(t[p * 2], t[p * 2 + 1]);
    }
  }
} AC;
int n;
long long x;
vector<long long> Ini;
long long ans;
void KillMeSoftly(int l, int r) {
  if (r == l) return;
  long long val = AC.get(l, r), val2 = abs(val - x);
  ans = max(ans, A.get(0, n) + x - val + val2);
}
void YeaBoi() { ans = max(ans, A.get(0, n) + 2 * x); }
int find_z(int l, int r) {
  while (r - l > 1) {
    int m = (l + r) / 2;
    if (Z.get(l, m))
      r = m;
    else
      l = m;
  }
  return l;
}
void Cacona(int p) {
  long long val1 = D.get(p, p + 1), val2 = D.get(p + 1, p + 2);
  A.set(p, abs(val1 + x));
  A.set(p + 1, abs(val2 - x));
  ans = max(ans, A.get(0, n));
  A.set(p, abs(val1));
  A.set(p + 1, abs(val2));
}
int main() {
  while (scanf("%d", &n) == 1) {
    Ini.resize(n);
    for (int i = (0); i < (int)(n); i++) scanf("%lld", &Ini[i]);
    n--;
    D.init(n);
    A.init(n);
    Z.init(n);
    AC.init(n);
    for (int i = (0); i < (int)(n); i++) {
      D[i] = Ini[i + 1] - Ini[i];
      A[i] = AC[i] = abs(D[i]);
      Z[i] = (D[i] == 0);
    }
    D.updall();
    A.updall();
    Z.updall();
    AC.updall();
    int q;
    scanf("%d", &q);
    for (int cs = (0); cs < (int)(q); cs++) {
      int l, r, op;
      ans = -INF;
      scanf("%d %d %d %lld", &op, &l, &r, &x);
      l--;
      if (op == 1) {
        l--;
        int cntz = Z.get(l, r);
        switch (cntz) {
          case 0: {
            if ((A.get(l, r) == abs(D.get(l, r)))) {
              if (D[l] > 0)
                KillMeSoftly(l + 1, r);
              else
                KillMeSoftly(l, r - 1);
              break;
            }
            if (D[l] > 0) {
              YeaBoi();
              break;
            }
            int i = l + 1, d = r, m;
            while (d - i > 1) {
              m = (i + d) / 2;
              if ((A.get(l, m) == abs(D.get(l, m))))
                i = m;
              else
                d = m;
            }
            if ((A.get(i, r) == abs(D.get(i, r)))) {
              Cacona(i - 1);
              KillMeSoftly(l, i - 1);
              KillMeSoftly(i + 1, r);
            } else
              YeaBoi();
            break;
          }
          case 1: {
            int d = find_z(l, r);
            if (d > l &&
                ((D[d - 1] > 0) || (!(A.get(l, d) == abs(D.get(l, d)))))) {
              YeaBoi();
              break;
            }
            if (d < r - 1 && ((D[d + 1] < 0) ||
                              (!(A.get(d + 1, r) == abs(D.get(d + 1, r)))))) {
              YeaBoi();
              break;
            }
            KillMeSoftly(l, d);
            KillMeSoftly(d + 1, r);
            break;
          }
          default: {
            YeaBoi();
            break;
          }
        }
        printf("%lld\n", ans);
      } else {
        l--;
        r--;
        if (l >= 0) {
          long long val = D.get(l, l + 1) + x;
          D.set(l, val);
          A.set(l, abs(val));
          AC.set(l, abs(val));
          Z.set(l, (val == 0 ? 1 : 0));
        }
        if (r < n) {
          long long val = D.get(r, r + 1) - x;
          D.set(r, val);
          A.set(r, abs(val));
          AC.set(r, abs(val));
          Z.set(r, (val == 0 ? 1 : 0));
        }
      }
    }
  }
  return 0;
}

```