#include <bits/stdc++.h>
using namespace std;
int a[100005];
long long b[100005];
long long f[100005 << 2];
void update(int rt, int l, int r, int pos) {
  if (l == r) {
    long long t = 0;
    if (b[l - 1] > 0) t += b[l - 1];
    if (b[l] < 0) t -= b[l];
    f[rt] = t;
    return;
  }
  int mid = l + r >> 1;
  if (pos <= mid)
    update(rt << 1, l, mid, pos);
  else
    update(rt << 1 | 1, mid + 1, r, pos);
  f[rt] = min(f[rt << 1], f[rt << 1 | 1]);
}
long long query(int rt, int l, int r, int L, int R) {
  if (L <= l && r <= R) {
    return f[rt];
  }
  int mid = l + r >> 1;
  if (R <= mid)
    return query(rt << 1, l, mid, L, R);
  else if (L > mid)
    return query(rt << 1 | 1, mid + 1, r, L, R);
  else
    return min(query(rt << 1, l, mid, L, R),
               query(rt << 1 | 1, mid + 1, r, L, R));
}
long long sum;
int n, m, op, l, r, x;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= n - 1; ++i) {
    b[i] = a[i] - a[i + 1];
    sum += abs(b[i]);
    if (i > 1) update(1, 2, n - 1, i);
  }
  scanf("%d", &m);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d%d", &op, &l, &r, &x);
    if (op == 1) {
      if (l == r) {
        printf("%I64d\n", sum - abs(b[l - 1]) + abs(b[l - 1] - x) - abs(b[l]) +
                              abs(b[l] + x));
      } else {
        long long t = query(1, 2, n - 1, l, r);
        if (t >= x)
          printf("%I64d\n", sum);
        else
          printf("%I64d\n", sum + (x - t) * 2);
      }
    } else {
      sum -= abs(b[l - 1]);
      sum -= abs(b[r]);
      b[l - 1] -= x;
      b[r] += x;
      sum += abs(b[l - 1]);
      sum += abs(b[r]);
      update(1, 2, n - 1, l);
      if (l > 2) update(1, 2, n - 1, l - 1);
      update(1, 2, n - 1, r);
      if (r < n - 1) update(1, 2, n - 1, r + 1);
    }
  }
}

### 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;
int a[100005];
long long b[100005];
long long f[100005 << 2];
void update(int rt, int l, int r, int pos) {
  if (l == r) {
    long long t = 0;
    if (b[l - 1] > 0) t += b[l - 1];
    if (b[l] < 0) t -= b[l];
    f[rt] = t;
    return;
  }
  int mid = l + r >> 1;
  if (pos <= mid)
    update(rt << 1, l, mid, pos);
  else
    update(rt << 1 | 1, mid + 1, r, pos);
  f[rt] = min(f[rt << 1], f[rt << 1 | 1]);
}
long long query(int rt, int l, int r, int L, int R) {
  if (L <= l && r <= R) {
    return f[rt];
  }
  int mid = l + r >> 1;
  if (R <= mid)
    return query(rt << 1, l, mid, L, R);
  else if (L > mid)
    return query(rt << 1 | 1, mid + 1, r, L, R);
  else
    return min(query(rt << 1, l, mid, L, R),
               query(rt << 1 | 1, mid + 1, r, L, R));
}
long long sum;
int n, m, op, l, r, x;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= n - 1; ++i) {
    b[i] = a[i] - a[i + 1];
    sum += abs(b[i]);
    if (i > 1) update(1, 2, n - 1, i);
  }
  scanf("%d", &m);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d%d", &op, &l, &r, &x);
    if (op == 1) {
      if (l == r) {
        printf("%I64d\n", sum - abs(b[l - 1]) + abs(b[l - 1] - x) - abs(b[l]) +
                              abs(b[l] + x));
      } else {
        long long t = query(1, 2, n - 1, l, r);
        if (t >= x)
          printf("%I64d\n", sum);
        else
          printf("%I64d\n", sum + (x - t) * 2);
      }
    } else {
      sum -= abs(b[l - 1]);
      sum -= abs(b[r]);
      b[l - 1] -= x;
      b[r] += x;
      sum += abs(b[l - 1]);
      sum += abs(b[r]);
      update(1, 2, n - 1, l);
      if (l > 2) update(1, 2, n - 1, l - 1);
      update(1, 2, n - 1, r);
      if (r < n - 1) update(1, 2, n - 1, r + 1);
    }
  }
}

```