#include <bits/stdc++.h>
const int N = 100005;
const long long inf = 0x3f3f3f3f3f3f3f3f;
int n, m;
long long a[N], max[N << 2], ans;
void pushup(int o) { max[o] = std::max(max[o << 1], max[o << 1 | 1]); }
void maintain(int pos, int o = 1, int l = 2, int r = n - 1) {
  if (l == r) {
    max[o] = std::min(a[l - 1], 0LL) - std::max(a[l], 0LL);
    return;
  }
  int mid = l + r >> 1;
  if (pos <= mid)
    maintain(pos, o << 1, l, mid);
  else
    maintain(pos, o << 1 | 1, mid + 1, r);
  pushup(o);
}
void modify(int pos, int x) {
  ans -= std::abs(a[pos]), ans += std::abs(a[pos] += x);
  if (pos > 1) maintain(pos);
  if (pos < n - 1) maintain(pos + 1);
}
long long query(int L, int R, int o = 1, int l = 2, int r = n - 1) {
  if (L <= l && R >= r) return max[o];
  int mid = l + r >> 1;
  long long ret = -inf;
  if (L <= mid) ret = std::max(ret, query(L, R, o << 1, l, mid));
  if (R > mid) ret = std::max(ret, query(L, R, o << 1 | 1, mid + 1, r));
  return ret;
}
int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  std::cin >> n;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  for (int i = 1; i < n; ++i) ans += std::abs(a[i] = a[i + 1] - a[i]);
  for (int i = 2; i < n; ++i) maintain(i);
  std::cin >> m;
  while (m--) {
    int opt, l, r, x;
    std::cin >> opt >> l >> r >> x;
    if (opt == 1) {
      long long d;
      if (l == r) {
        d = 0;
        if (l != 1) d += std::abs(a[l - 1] + x) - std::abs(a[l - 1]);
        if (l != n) d += std::abs(a[l] - x) - std::abs(a[l]);
      } else {
        d = std::max(2 * (query(l, r) + x), 0LL);
        if (l == 1) d = std::max(d, std::abs(a[1] - x) - std::abs(a[1]));
        if (r == n)
          d = std::max(d, std::abs(a[n - 1] + x) - std::abs(a[n - 1]));
      }
      std::cout << ans + d << '\n';
    } else {
      if (l > 1) modify(l - 1, x);
      if (r < n) modify(r, -x);
    }
  }
  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>
const int N = 100005;
const long long inf = 0x3f3f3f3f3f3f3f3f;
int n, m;
long long a[N], max[N << 2], ans;
void pushup(int o) { max[o] = std::max(max[o << 1], max[o << 1 | 1]); }
void maintain(int pos, int o = 1, int l = 2, int r = n - 1) {
  if (l == r) {
    max[o] = std::min(a[l - 1], 0LL) - std::max(a[l], 0LL);
    return;
  }
  int mid = l + r >> 1;
  if (pos <= mid)
    maintain(pos, o << 1, l, mid);
  else
    maintain(pos, o << 1 | 1, mid + 1, r);
  pushup(o);
}
void modify(int pos, int x) {
  ans -= std::abs(a[pos]), ans += std::abs(a[pos] += x);
  if (pos > 1) maintain(pos);
  if (pos < n - 1) maintain(pos + 1);
}
long long query(int L, int R, int o = 1, int l = 2, int r = n - 1) {
  if (L <= l && R >= r) return max[o];
  int mid = l + r >> 1;
  long long ret = -inf;
  if (L <= mid) ret = std::max(ret, query(L, R, o << 1, l, mid));
  if (R > mid) ret = std::max(ret, query(L, R, o << 1 | 1, mid + 1, r));
  return ret;
}
int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  std::cin >> n;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  for (int i = 1; i < n; ++i) ans += std::abs(a[i] = a[i + 1] - a[i]);
  for (int i = 2; i < n; ++i) maintain(i);
  std::cin >> m;
  while (m--) {
    int opt, l, r, x;
    std::cin >> opt >> l >> r >> x;
    if (opt == 1) {
      long long d;
      if (l == r) {
        d = 0;
        if (l != 1) d += std::abs(a[l - 1] + x) - std::abs(a[l - 1]);
        if (l != n) d += std::abs(a[l] - x) - std::abs(a[l]);
      } else {
        d = std::max(2 * (query(l, r) + x), 0LL);
        if (l == 1) d = std::max(d, std::abs(a[1] - x) - std::abs(a[1]));
        if (r == n)
          d = std::max(d, std::abs(a[n - 1] + x) - std::abs(a[n - 1]));
      }
      std::cout << ans + d << '\n';
    } else {
      if (l > 1) modify(l - 1, x);
      if (r < n) modify(r, -x);
    }
  }
  return 0;
}

```