#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e5 + 5;
long long n, q, f;
long long a[maxn], c[maxn];
struct segment_tree {
  struct node {
    long long l, r, mn;
  } t[maxn << 2];
  void pushup(long long p) { t[p].mn = min(t[p << 1].mn, t[p << 1 | 1].mn); }
  inline void build(long long p, long long l, long long r) {
    t[p].l = l;
    t[p].r = r;
    if (l == r) {
      if (l > 1) t[p].mn = max(c[l - 1], 0ll) + max(-c[l], 0ll);
      return;
    }
    long long mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushup(p);
  }
  inline long long query(long long p, long long x, long long y) {
    long long l = t[p].l, r = t[p].r;
    if (l >= x && r <= y) return t[p].mn;
    long long mid = l + r >> 1, ans = 1e9;
    if (mid >= x) ans = min(ans, query(p << 1, x, y));
    if (mid < y) ans = min(ans, query(p << 1 | 1, x, y));
    return ans;
  }
  inline void update(long long p, long long x, long long k) {
    long long l = t[p].l, r = t[p].r;
    if (l == r) {
      f += abs(c[l] + k) - abs(c[l]);
      c[l] += k;
      t[p].mn = max(c[l - 1], 0ll) + max(-c[l], 0ll);
      if (k && x < n - 1) update(1, x + 1, 0);
      return;
    }
    long long mid = l + r >> 1;
    if (mid >= x)
      update(p << 1, x, k);
    else
      update(p << 1 | 1, x, k);
    pushup(p);
  }
} T;
inline void read(long long &x) {
  long long f = 1;
  x = 0;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  x *= f;
}
inline void write(long long x) {
  long long stack[105], top = 0;
  if (x == 0) {
    putchar('0');
    putchar('\n');
    return;
  }
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  while (x) {
    stack[++top] = x % 10;
    x /= 10;
  }
  while (top) putchar(stack[top--] + '0');
  putchar('\n');
}
signed main() {
  read(n);
  for (long long i = 1; i <= n; i++) read(a[i]);
  for (long long i = 1; i < n; i++) c[i] = a[i] - a[i + 1], f += abs(c[i]);
  read(q);
  T.build(1, 1, n - 1);
  for (long long cxk = 1, op, l, r, x; cxk <= q; cxk++) {
    read(op);
    read(l);
    read(r);
    read(x);
    if (op == 1) {
      if (l == r) {
        if (l == 1)
          write(f + abs(c[l] + x) - abs(c[l]));
        else if (l == n)
          write(f + abs(c[l - 1] - x) - abs(c[l - 1]));
        else
          write(f + abs(c[l] + x) - abs(c[l]) + abs(c[l - 1] - x) -
                abs(c[l - 1]));
      } else {
        long long tt = 2 * (x - T.query(1, l > 1 ? l : 2, r));
        if (l == 1) tt = max(tt, abs(a[l] + x) - abs(a[l]));
        if (r == n) tt = max(tt, abs(a[r - 1] - x) - abs(a[r - 1]));
        write(f + max(0ll, tt));
      }
    } else {
      if (l > 1) T.update(1, l - 1, -x);
      if (r < n) T.update(1, r, x);
    }
  }
  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 maxn = 1e5 + 5;
long long n, q, f;
long long a[maxn], c[maxn];
struct segment_tree {
  struct node {
    long long l, r, mn;
  } t[maxn << 2];
  void pushup(long long p) { t[p].mn = min(t[p << 1].mn, t[p << 1 | 1].mn); }
  inline void build(long long p, long long l, long long r) {
    t[p].l = l;
    t[p].r = r;
    if (l == r) {
      if (l > 1) t[p].mn = max(c[l - 1], 0ll) + max(-c[l], 0ll);
      return;
    }
    long long mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushup(p);
  }
  inline long long query(long long p, long long x, long long y) {
    long long l = t[p].l, r = t[p].r;
    if (l >= x && r <= y) return t[p].mn;
    long long mid = l + r >> 1, ans = 1e9;
    if (mid >= x) ans = min(ans, query(p << 1, x, y));
    if (mid < y) ans = min(ans, query(p << 1 | 1, x, y));
    return ans;
  }
  inline void update(long long p, long long x, long long k) {
    long long l = t[p].l, r = t[p].r;
    if (l == r) {
      f += abs(c[l] + k) - abs(c[l]);
      c[l] += k;
      t[p].mn = max(c[l - 1], 0ll) + max(-c[l], 0ll);
      if (k && x < n - 1) update(1, x + 1, 0);
      return;
    }
    long long mid = l + r >> 1;
    if (mid >= x)
      update(p << 1, x, k);
    else
      update(p << 1 | 1, x, k);
    pushup(p);
  }
} T;
inline void read(long long &x) {
  long long f = 1;
  x = 0;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  x *= f;
}
inline void write(long long x) {
  long long stack[105], top = 0;
  if (x == 0) {
    putchar('0');
    putchar('\n');
    return;
  }
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  while (x) {
    stack[++top] = x % 10;
    x /= 10;
  }
  while (top) putchar(stack[top--] + '0');
  putchar('\n');
}
signed main() {
  read(n);
  for (long long i = 1; i <= n; i++) read(a[i]);
  for (long long i = 1; i < n; i++) c[i] = a[i] - a[i + 1], f += abs(c[i]);
  read(q);
  T.build(1, 1, n - 1);
  for (long long cxk = 1, op, l, r, x; cxk <= q; cxk++) {
    read(op);
    read(l);
    read(r);
    read(x);
    if (op == 1) {
      if (l == r) {
        if (l == 1)
          write(f + abs(c[l] + x) - abs(c[l]));
        else if (l == n)
          write(f + abs(c[l - 1] - x) - abs(c[l - 1]));
        else
          write(f + abs(c[l] + x) - abs(c[l]) + abs(c[l - 1] - x) -
                abs(c[l - 1]));
      } else {
        long long tt = 2 * (x - T.query(1, l > 1 ? l : 2, r));
        if (l == 1) tt = max(tt, abs(a[l] + x) - abs(a[l]));
        if (r == n) tt = max(tt, abs(a[r - 1] - x) - abs(a[r - 1]));
        write(f + max(0ll, tt));
      }
    } else {
      if (l > 1) T.update(1, l - 1, -x);
      if (r < n) T.update(1, r, x);
    }
  }
  return 0;
}

```