#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1000000007;
const long long BIG = 1446803456761533460LL;
const int Big = 336860180;
const long long int INF = LONG_LONG_MAX;
const long long int adj4[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
const long long int adj8[8][2] = {{0, 1},   {0, -1}, {1, 0},  {-1, 0},
                                  {-1, -1}, {1, -1}, {-1, 1}, {1, 1}};
long long int clk_ar[10];
long long int gcd(long long int a, long long int b) {
  return b == 0 ? a : gcd(b, a % b);
}
long long int powMod(long long int a, long long int b) {
  long long int n = 1;
  long long int p = a;
  while (b > 0) {
    if (b % 2 == 1) {
      n *= p;
      n %= MOD;
    }
    p *= p;
    p %= MOD;
    b /= 2;
  }
  return n;
}
long long int modularInverse(long long int a) { return powMod(a, MOD - 2); }
stringstream sss;
const long long int maxn = 100010;
long long int ar[maxn];
long long int df[maxn];
long long int val[maxn];
long long int seg[maxn * 4];
long long int Z(long long int x) { return max(0LL, x); }
void build(long long int x, long long int l, long long int r) {
  if (r - l == 1) {
    seg[x] = val[l];
  } else {
    long long int mid = (l + r) / 2;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid, r);
    seg[x] = min(seg[x * 2], seg[x * 2 + 1]);
  }
}
void update(long long int pos, long long int x, long long int l,
            long long int r) {
  if (r - l == 1) {
    seg[x] = val[l];
  } else {
    long long int mid = (l + r) / 2;
    if (pos < mid) {
      update(pos, x * 2, l, mid);
    } else {
      update(pos, x * 2 + 1, mid, r);
    }
    seg[x] = min(seg[x * 2], seg[x * 2 + 1]);
  }
}
long long int get(long long int li, long long int ri, long long int x,
                  long long int l, long long int r) {
  if (li >= r || l >= ri) {
    return BIG;
  } else if (li <= l && r <= ri) {
    return seg[x];
  } else {
    long long int mid = (l + r) / 2;
    return min(get(li, ri, x * 2, l, mid), get(li, ri, x * 2 + 1, mid, r));
  }
}
void MAIN() {
  long long int n;
  cin >> n;
  for (long long int i = 0; i < (n); ++i) {
    cin >> ar[i + 1];
  }
  ar[0] = -BIG;
  ar[n + 1] = -BIG;
  n += 2;
  for (long long int i = 0; i < (n - 1); ++i) {
    df[i] = ar[i + 1] - ar[i];
  }
  for (long long int i = (1); i < (n - 1); ++i) {
    val[i] = Z(-df[i - 1]) + Z(df[i]);
  }
  long long int fa = 0;
  for (long long int i = (1); i < (n - 2); ++i) {
    fa += abs(df[i]);
  }
  build(1, 0, n);
  long long int Q;
  cin >> Q;
  for (long long int q = 0; q < (Q); ++q) {
    long long int typ, l, r, x;
    cin >> typ >> l >> r >> x;
    ++r;
    if (typ == 1) {
      if (r - l == 1) {
        long long int ans = fa;
        if (l != 1) {
          ans = ans - abs(df[l - 1]) + abs(df[l - 1] + x);
        }
        if (r != n - 1) {
          ans = ans - abs(df[r - 1]) + abs(df[r - 1] - x);
        }
        cout << (ans) << '\n';
      } else {
        long long int delta = -BIG;
        if (l == 1) {
          delta = max(delta, (Z(-df[1] + x) + df[1]));
          ++l;
        }
        if (r == n - 1) {
          delta = max(delta, (Z(df[n - 3] + x) - df[n - 3]));
          --r;
        }
        long long int mn = get(l, r, 1, 0, n);
        delta = max(delta, (Z(x * 2 - mn * 2)));
        cout << (fa + delta) << '\n';
      }
    } else if (typ == 2) {
      fa -= abs(df[l - 1]);
      fa -= abs(df[r - 1]);
      df[l - 1] += x;
      df[r - 1] -= x;
      val[l - 1] = Z(-df[l - 2]) + Z(df[l - 1]);
      val[l] = Z(-df[l - 1]) + Z(df[l]);
      val[r - 1] = Z(-df[r - 2]) + Z(df[r - 1]);
      val[r] = Z(-df[r - 1]) + Z(df[r]);
      update(l - 1, 1, 0, n);
      update(l, 1, 0, n);
      update(r - 1, 1, 0, n);
      update(r, 1, 0, n);
      fa += abs(df[l - 1]);
      fa += abs(df[r - 1]);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  sss << R"(
5
1 2 3 5 5
1
1 1 5 2
5
10 5 1 5 10
1
1 1 5 1
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
5
1 2 3 4 5
4
1 2 4 2
2 2 4 1
2 3 4 1
1 2 4 2
    )";
  MAIN();
  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 int MOD = 1000000007;
const long long BIG = 1446803456761533460LL;
const int Big = 336860180;
const long long int INF = LONG_LONG_MAX;
const long long int adj4[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
const long long int adj8[8][2] = {{0, 1},   {0, -1}, {1, 0},  {-1, 0},
                                  {-1, -1}, {1, -1}, {-1, 1}, {1, 1}};
long long int clk_ar[10];
long long int gcd(long long int a, long long int b) {
  return b == 0 ? a : gcd(b, a % b);
}
long long int powMod(long long int a, long long int b) {
  long long int n = 1;
  long long int p = a;
  while (b > 0) {
    if (b % 2 == 1) {
      n *= p;
      n %= MOD;
    }
    p *= p;
    p %= MOD;
    b /= 2;
  }
  return n;
}
long long int modularInverse(long long int a) { return powMod(a, MOD - 2); }
stringstream sss;
const long long int maxn = 100010;
long long int ar[maxn];
long long int df[maxn];
long long int val[maxn];
long long int seg[maxn * 4];
long long int Z(long long int x) { return max(0LL, x); }
void build(long long int x, long long int l, long long int r) {
  if (r - l == 1) {
    seg[x] = val[l];
  } else {
    long long int mid = (l + r) / 2;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid, r);
    seg[x] = min(seg[x * 2], seg[x * 2 + 1]);
  }
}
void update(long long int pos, long long int x, long long int l,
            long long int r) {
  if (r - l == 1) {
    seg[x] = val[l];
  } else {
    long long int mid = (l + r) / 2;
    if (pos < mid) {
      update(pos, x * 2, l, mid);
    } else {
      update(pos, x * 2 + 1, mid, r);
    }
    seg[x] = min(seg[x * 2], seg[x * 2 + 1]);
  }
}
long long int get(long long int li, long long int ri, long long int x,
                  long long int l, long long int r) {
  if (li >= r || l >= ri) {
    return BIG;
  } else if (li <= l && r <= ri) {
    return seg[x];
  } else {
    long long int mid = (l + r) / 2;
    return min(get(li, ri, x * 2, l, mid), get(li, ri, x * 2 + 1, mid, r));
  }
}
void MAIN() {
  long long int n;
  cin >> n;
  for (long long int i = 0; i < (n); ++i) {
    cin >> ar[i + 1];
  }
  ar[0] = -BIG;
  ar[n + 1] = -BIG;
  n += 2;
  for (long long int i = 0; i < (n - 1); ++i) {
    df[i] = ar[i + 1] - ar[i];
  }
  for (long long int i = (1); i < (n - 1); ++i) {
    val[i] = Z(-df[i - 1]) + Z(df[i]);
  }
  long long int fa = 0;
  for (long long int i = (1); i < (n - 2); ++i) {
    fa += abs(df[i]);
  }
  build(1, 0, n);
  long long int Q;
  cin >> Q;
  for (long long int q = 0; q < (Q); ++q) {
    long long int typ, l, r, x;
    cin >> typ >> l >> r >> x;
    ++r;
    if (typ == 1) {
      if (r - l == 1) {
        long long int ans = fa;
        if (l != 1) {
          ans = ans - abs(df[l - 1]) + abs(df[l - 1] + x);
        }
        if (r != n - 1) {
          ans = ans - abs(df[r - 1]) + abs(df[r - 1] - x);
        }
        cout << (ans) << '\n';
      } else {
        long long int delta = -BIG;
        if (l == 1) {
          delta = max(delta, (Z(-df[1] + x) + df[1]));
          ++l;
        }
        if (r == n - 1) {
          delta = max(delta, (Z(df[n - 3] + x) - df[n - 3]));
          --r;
        }
        long long int mn = get(l, r, 1, 0, n);
        delta = max(delta, (Z(x * 2 - mn * 2)));
        cout << (fa + delta) << '\n';
      }
    } else if (typ == 2) {
      fa -= abs(df[l - 1]);
      fa -= abs(df[r - 1]);
      df[l - 1] += x;
      df[r - 1] -= x;
      val[l - 1] = Z(-df[l - 2]) + Z(df[l - 1]);
      val[l] = Z(-df[l - 1]) + Z(df[l]);
      val[r - 1] = Z(-df[r - 2]) + Z(df[r - 1]);
      val[r] = Z(-df[r - 1]) + Z(df[r]);
      update(l - 1, 1, 0, n);
      update(l, 1, 0, n);
      update(r - 1, 1, 0, n);
      update(r, 1, 0, n);
      fa += abs(df[l - 1]);
      fa += abs(df[r - 1]);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  sss << R"(
5
1 2 3 5 5
1
1 1 5 2
5
10 5 1 5 10
1
1 1 5 1
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
5
1 2 3 4 5
4
1 2 4 2
2 2 4 1
2 3 4 1
1 2 4 2
    )";
  MAIN();
  return 0;
}

```