#include <bits/stdc++.h>
using namespace std;
long long bit[123456], seg[5][412345], a[123456];
long long iinf;
long long updatebit(long long pos, long long val) {
  while (pos < 123456) {
    bit[pos] += val;
    pos += pos & (-pos);
  }
  return 0;
}
long long querybit(long long pos) {
  long long ans = 0;
  while (pos > 0) {
    ans += bit[pos];
    pos -= pos & (-pos);
  }
  return ans;
}
long long getval(long long pos) { return querybit(pos) + a[pos]; }
long long buildseg(long long node, long long s, long long e) {
  long long i;
  if (s == e) {
    seg[0][node] = (a[s - 1] - a[s]) + (a[s] - a[s + 1]);
    seg[1][node] = (a[s - 1] - a[s]) - 1 * (a[s] - a[s + 1]);
    seg[2][node] = -1 * (a[s - 1] - a[s]) + (a[s] - a[s + 1]);
    seg[3][node] = -1 * (a[s - 1] - a[s]) - 1 * (a[s] - a[s + 1]);
    seg[4][node] = seg[0][node];
    for (i = 0; i < 4; i++) {
      seg[4][node] = max(seg[4][node], seg[i][node]);
    }
    for (i = 0; i < 4; i++) {
      seg[i][node] -= seg[4][node];
    }
    return 0;
  }
  long long mid = (s + e) / 2;
  buildseg(2 * node, s, mid);
  buildseg(2 * node + 1, mid + 1, e);
  for (i = 0; i < 4; i++) {
    seg[i][node] = max(seg[i][2 * node], seg[i][2 * node + 1]);
  }
  return 0;
}
long long update(long long node, long long s, long long e, long long p) {
  long long i;
  if (s == e) {
    long long val1 = getval(s - 1);
    long long val2 = getval(s);
    long long val3 = getval(s + 1);
    seg[0][node] = (val1 - val2) + (val2 - val3);
    seg[1][node] = (val1 - val2) - 1 * (val2 - val3);
    seg[2][node] = -1 * (val1 - val2) + (val2 - val3);
    seg[3][node] = -1 * (val1 - val2) - 1 * (val2 - val3);
    seg[4][node] = seg[0][node];
    for (i = 0; i < 4; i++) {
      seg[4][node] = max(seg[4][node], seg[i][node]);
    }
    for (i = 0; i < 4; i++) {
      seg[i][node] -= seg[4][node];
    }
    return 0;
  }
  long long mid = (s + e) / 2;
  if (p <= mid) {
    update(2 * node, s, mid, p);
  } else {
    update(2 * node + 1, mid + 1, e, p);
  }
  for (i = 0; i < 4; i++) {
    seg[i][node] = max(seg[i][2 * node], seg[i][2 * node + 1]);
  }
  return 0;
}
long long query(long long node, long long s, long long e, long long l,
                long long r, long long x) {
  if (e < l || r < s) return iinf;
  if (l <= s && e <= r) {
    long long maxi = seg[0][node];
    maxi = max(seg[1][node] - 2 * x, seg[2][node] + 2 * x);
    maxi = max(maxi, seg[0][node]);
    maxi = max(maxi, seg[3][node]);
    return maxi;
  }
  long long mid = (s + e) / 2;
  long long a = query(2 * node, s, mid, l, r, x);
  long long b = query(2 * node + 1, mid + 1, e, l, r, x);
  return max(a, b);
}
int main() {
  std::ios::sync_with_stdio(false);
  long long n;
  iinf = (1000 * 1000 * 1000 + 5);
  iinf *= (1000 * 1000 * 1000 + 5);
  iinf *= -1;
  cin >> n;
  long long i;
  for (i = 1; i < n + 1; i++) {
    cin >> a[i];
  }
  long long ans = 0;
  for (i = 1; i < n; i++) {
    ans += abs(a[i] - a[i + 1]);
  }
  long long q;
  cin >> q;
  long long typ, l, r, x, maxi, val1, val2;
  buildseg(1, 2, n - 1);
  for (i = 0; i < q; i++) {
    cin >> typ >> l >> r >> x;
    if (typ == 1) {
      maxi = iinf;
      if (r > 1 && l < n)
        maxi = query(1, 2, n - 1, max(l, 2LL), min(r, n - 1), x);
      if (l == 1) {
        val1 = getval(1);
        val2 = getval(2);
        maxi = max(maxi, abs(val1 + x - val2) - abs(val1 - val2));
      }
      if (r == n) {
        val1 = getval(n - 1);
        val2 = getval(n);
        maxi = max(maxi, abs(val1 + x - val2) - abs(val1 - val2));
      }
      cout << ans + maxi << endl;
    } else {
      if (l != 1) {
        ans -= abs(getval(l - 1) - getval(l));
      }
      if (r != n) {
        ans -= abs(getval(r) - getval(r + 1));
      }
      updatebit(l, x);
      updatebit(r + 1, -1 * x);
      if (r != n) {
        ans += abs(getval(r) - getval(r + 1));
        if (r != 1) update(1, 2, n - 1, r);
        update(1, 2, n - 1, r + 1);
      }
      if (l != 1) {
        if (l != n) update(1, 2, n - 1, l);
        update(1, 2, n - 1, l - 1);
        ans += abs(getval(l - 1) - getval(l));
      }
    }
  }
  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;
long long bit[123456], seg[5][412345], a[123456];
long long iinf;
long long updatebit(long long pos, long long val) {
  while (pos < 123456) {
    bit[pos] += val;
    pos += pos & (-pos);
  }
  return 0;
}
long long querybit(long long pos) {
  long long ans = 0;
  while (pos > 0) {
    ans += bit[pos];
    pos -= pos & (-pos);
  }
  return ans;
}
long long getval(long long pos) { return querybit(pos) + a[pos]; }
long long buildseg(long long node, long long s, long long e) {
  long long i;
  if (s == e) {
    seg[0][node] = (a[s - 1] - a[s]) + (a[s] - a[s + 1]);
    seg[1][node] = (a[s - 1] - a[s]) - 1 * (a[s] - a[s + 1]);
    seg[2][node] = -1 * (a[s - 1] - a[s]) + (a[s] - a[s + 1]);
    seg[3][node] = -1 * (a[s - 1] - a[s]) - 1 * (a[s] - a[s + 1]);
    seg[4][node] = seg[0][node];
    for (i = 0; i < 4; i++) {
      seg[4][node] = max(seg[4][node], seg[i][node]);
    }
    for (i = 0; i < 4; i++) {
      seg[i][node] -= seg[4][node];
    }
    return 0;
  }
  long long mid = (s + e) / 2;
  buildseg(2 * node, s, mid);
  buildseg(2 * node + 1, mid + 1, e);
  for (i = 0; i < 4; i++) {
    seg[i][node] = max(seg[i][2 * node], seg[i][2 * node + 1]);
  }
  return 0;
}
long long update(long long node, long long s, long long e, long long p) {
  long long i;
  if (s == e) {
    long long val1 = getval(s - 1);
    long long val2 = getval(s);
    long long val3 = getval(s + 1);
    seg[0][node] = (val1 - val2) + (val2 - val3);
    seg[1][node] = (val1 - val2) - 1 * (val2 - val3);
    seg[2][node] = -1 * (val1 - val2) + (val2 - val3);
    seg[3][node] = -1 * (val1 - val2) - 1 * (val2 - val3);
    seg[4][node] = seg[0][node];
    for (i = 0; i < 4; i++) {
      seg[4][node] = max(seg[4][node], seg[i][node]);
    }
    for (i = 0; i < 4; i++) {
      seg[i][node] -= seg[4][node];
    }
    return 0;
  }
  long long mid = (s + e) / 2;
  if (p <= mid) {
    update(2 * node, s, mid, p);
  } else {
    update(2 * node + 1, mid + 1, e, p);
  }
  for (i = 0; i < 4; i++) {
    seg[i][node] = max(seg[i][2 * node], seg[i][2 * node + 1]);
  }
  return 0;
}
long long query(long long node, long long s, long long e, long long l,
                long long r, long long x) {
  if (e < l || r < s) return iinf;
  if (l <= s && e <= r) {
    long long maxi = seg[0][node];
    maxi = max(seg[1][node] - 2 * x, seg[2][node] + 2 * x);
    maxi = max(maxi, seg[0][node]);
    maxi = max(maxi, seg[3][node]);
    return maxi;
  }
  long long mid = (s + e) / 2;
  long long a = query(2 * node, s, mid, l, r, x);
  long long b = query(2 * node + 1, mid + 1, e, l, r, x);
  return max(a, b);
}
int main() {
  std::ios::sync_with_stdio(false);
  long long n;
  iinf = (1000 * 1000 * 1000 + 5);
  iinf *= (1000 * 1000 * 1000 + 5);
  iinf *= -1;
  cin >> n;
  long long i;
  for (i = 1; i < n + 1; i++) {
    cin >> a[i];
  }
  long long ans = 0;
  for (i = 1; i < n; i++) {
    ans += abs(a[i] - a[i + 1]);
  }
  long long q;
  cin >> q;
  long long typ, l, r, x, maxi, val1, val2;
  buildseg(1, 2, n - 1);
  for (i = 0; i < q; i++) {
    cin >> typ >> l >> r >> x;
    if (typ == 1) {
      maxi = iinf;
      if (r > 1 && l < n)
        maxi = query(1, 2, n - 1, max(l, 2LL), min(r, n - 1), x);
      if (l == 1) {
        val1 = getval(1);
        val2 = getval(2);
        maxi = max(maxi, abs(val1 + x - val2) - abs(val1 - val2));
      }
      if (r == n) {
        val1 = getval(n - 1);
        val2 = getval(n);
        maxi = max(maxi, abs(val1 + x - val2) - abs(val1 - val2));
      }
      cout << ans + maxi << endl;
    } else {
      if (l != 1) {
        ans -= abs(getval(l - 1) - getval(l));
      }
      if (r != n) {
        ans -= abs(getval(r) - getval(r + 1));
      }
      updatebit(l, x);
      updatebit(r + 1, -1 * x);
      if (r != n) {
        ans += abs(getval(r) - getval(r + 1));
        if (r != 1) update(1, 2, n - 1, r);
        update(1, 2, n - 1, r + 1);
      }
      if (l != 1) {
        if (l != n) update(1, 2, n - 1, l);
        update(1, 2, n - 1, l - 1);
        ans += abs(getval(l - 1) - getval(l));
      }
    }
  }
  return 0;
}

```