#include <bits/stdc++.h>
using namespace std;
inline char gc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline long long read() {
  long long x = 0;
  char ch = getchar();
  bool positive = 1;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') positive = 0;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return positive ? x : -x;
}
inline void write(long long a) {
  if (a >= 10) write(a / 10);
  putchar('0' + a % 10);
}
inline void writeln(long long a) {
  if (a < 0) {
    a = -a;
    putchar('-');
  }
  write(a);
  puts("");
}
const long long N = 100005;
long long c[N], tree[N << 2], p1[N << 2], p2[N << 2], q[N], tot, n, qq, a[N],
    sum;
inline void update(long long pos, long long de) {
  for (long long i = pos; i; i -= i & -i) c[i] += de;
}
inline long long get(long long pos) {
  long long ans = 0;
  if (!pos) return 0;
  for (long long i = pos; i < N; i += i & -i) ans += c[i];
  return ans;
}
inline long long ggg(long long pos) { return get(pos) - get(pos - 1); }
void insert(long long l, long long r, long long pos, long long nod) {
  if (l == r) {
    tree[nod] = abs(get(pos) - get(pos - 1));
    if (ggg(l) >= 0 && ggg(l + 1) <= 0)
      p1[nod] = pos;
    else
      p1[nod] = 0;
    if (ggg(l) <= 0 && ggg(l + 1) >= 0)
      p2[nod] = pos;
    else
      p2[nod] = 0;
    return;
  }
  long long mid = (l + r) >> 1;
  if (pos <= mid)
    insert(l, mid, pos, nod << 1);
  else
    insert(mid + 1, r, pos, nod << 1 | 1);
  tree[nod] = min(tree[nod << 1], tree[nod << 1 | 1]);
  p1[nod] = max(p1[nod << 1], p1[nod << 1 | 1]);
  p2[nod] = max(p2[nod << 1], p2[nod << 1 | 1]);
}
void ask(long long l, long long r, long long i, long long j, long long nod) {
  if (i > j) return;
  if (l == i && r == j) {
    q[++tot] = nod;
    return;
  }
  long long mid = (l + r) >> 1;
  if (j <= mid)
    ask(l, mid, i, j, nod << 1);
  else if (i > mid)
    ask(mid + 1, r, i, j, nod << 1 | 1);
  else {
    ask(l, mid, i, mid, nod << 1);
    ask(mid + 1, r, mid + 1, j, nod << 1 | 1);
  }
}
signed main() {
  n = read();
  for (long long i = 1; i <= n; i++) {
    a[i] = read();
    if (i > 1) sum += abs(a[i] - a[i - 1]);
    update(i, a[i]);
    update(i - 1, -a[i]);
  }
  qq = read();
  for (long long i = 1; i <= n; i++) insert(1, n, i, 1);
  for (long long i = 1; i <= qq; i++) {
    long long t = read(), l = read(), r = read(), x = read();
    if (t == 2) {
      sum += abs(get(l) + x - get(l - 1)) - abs(get(l) - get(l - 1));
      sum += abs(get(r + 1) - get(r) - x) - abs(get(r + 1) - get(r));
      update(l - 1, -x);
      update(r, x);
      insert(1, n, l - 1, 1);
      insert(1, n, l, 1);
      insert(1, n, l + 1, 1);
      insert(1, n, r - 1, 1);
      insert(1, n, r, 1);
      insert(1, n, r + 1, 1);
    } else {
      long long ans = -4e18;
      tot = 0;
      ask(1, n, l, r, 1);
      long long t = 0;
      for (long long i = 1; i <= tot; i++) t = max(t, p1[q[i]]);
      if (t) {
        writeln(sum + 2 * x);
        continue;
      }
      for (long long i = 1; i <= tot; i++) t = max(t, p2[q[i]]);
      if (t) {
        tot = 0;
        ask(1, n, l, t - 1, 1);
        for (long long i = 1; i <= tot; i++)
          ans = max(ans, sum + x + abs(tree[q[i]] - x) - abs(tree[q[i]]));
        ans = max(
            ans, sum + abs(get(t) - get(t - 1) + x) - abs(get(t) - get(t - 1)) +
                     abs(get(t + 1) - get(t) - x) - abs(get(t + 1) - get(t)));
        tot = 0;
        ask(1, n, t + 2, r + 1, 1);
        for (long long i = 1; i <= tot; i++)
          ans = max(ans, sum + x + abs(tree[q[i]] - x) - abs(tree[q[i]]));
      } else {
        tot = 0;
        if (ggg(l) >= 0)
          ask(1, n, l + 1, r + 1, 1);
        else
          ask(1, n, l, r, 1);
        for (long long i = 1; i <= tot; i++)
          ans = max(ans, sum + x + abs(tree[q[i]] - x) - abs(tree[q[i]]));
      }
      writeln(ans);
    }
  }
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;
inline char gc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline long long read() {
  long long x = 0;
  char ch = getchar();
  bool positive = 1;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') positive = 0;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return positive ? x : -x;
}
inline void write(long long a) {
  if (a >= 10) write(a / 10);
  putchar('0' + a % 10);
}
inline void writeln(long long a) {
  if (a < 0) {
    a = -a;
    putchar('-');
  }
  write(a);
  puts("");
}
const long long N = 100005;
long long c[N], tree[N << 2], p1[N << 2], p2[N << 2], q[N], tot, n, qq, a[N],
    sum;
inline void update(long long pos, long long de) {
  for (long long i = pos; i; i -= i & -i) c[i] += de;
}
inline long long get(long long pos) {
  long long ans = 0;
  if (!pos) return 0;
  for (long long i = pos; i < N; i += i & -i) ans += c[i];
  return ans;
}
inline long long ggg(long long pos) { return get(pos) - get(pos - 1); }
void insert(long long l, long long r, long long pos, long long nod) {
  if (l == r) {
    tree[nod] = abs(get(pos) - get(pos - 1));
    if (ggg(l) >= 0 && ggg(l + 1) <= 0)
      p1[nod] = pos;
    else
      p1[nod] = 0;
    if (ggg(l) <= 0 && ggg(l + 1) >= 0)
      p2[nod] = pos;
    else
      p2[nod] = 0;
    return;
  }
  long long mid = (l + r) >> 1;
  if (pos <= mid)
    insert(l, mid, pos, nod << 1);
  else
    insert(mid + 1, r, pos, nod << 1 | 1);
  tree[nod] = min(tree[nod << 1], tree[nod << 1 | 1]);
  p1[nod] = max(p1[nod << 1], p1[nod << 1 | 1]);
  p2[nod] = max(p2[nod << 1], p2[nod << 1 | 1]);
}
void ask(long long l, long long r, long long i, long long j, long long nod) {
  if (i > j) return;
  if (l == i && r == j) {
    q[++tot] = nod;
    return;
  }
  long long mid = (l + r) >> 1;
  if (j <= mid)
    ask(l, mid, i, j, nod << 1);
  else if (i > mid)
    ask(mid + 1, r, i, j, nod << 1 | 1);
  else {
    ask(l, mid, i, mid, nod << 1);
    ask(mid + 1, r, mid + 1, j, nod << 1 | 1);
  }
}
signed main() {
  n = read();
  for (long long i = 1; i <= n; i++) {
    a[i] = read();
    if (i > 1) sum += abs(a[i] - a[i - 1]);
    update(i, a[i]);
    update(i - 1, -a[i]);
  }
  qq = read();
  for (long long i = 1; i <= n; i++) insert(1, n, i, 1);
  for (long long i = 1; i <= qq; i++) {
    long long t = read(), l = read(), r = read(), x = read();
    if (t == 2) {
      sum += abs(get(l) + x - get(l - 1)) - abs(get(l) - get(l - 1));
      sum += abs(get(r + 1) - get(r) - x) - abs(get(r + 1) - get(r));
      update(l - 1, -x);
      update(r, x);
      insert(1, n, l - 1, 1);
      insert(1, n, l, 1);
      insert(1, n, l + 1, 1);
      insert(1, n, r - 1, 1);
      insert(1, n, r, 1);
      insert(1, n, r + 1, 1);
    } else {
      long long ans = -4e18;
      tot = 0;
      ask(1, n, l, r, 1);
      long long t = 0;
      for (long long i = 1; i <= tot; i++) t = max(t, p1[q[i]]);
      if (t) {
        writeln(sum + 2 * x);
        continue;
      }
      for (long long i = 1; i <= tot; i++) t = max(t, p2[q[i]]);
      if (t) {
        tot = 0;
        ask(1, n, l, t - 1, 1);
        for (long long i = 1; i <= tot; i++)
          ans = max(ans, sum + x + abs(tree[q[i]] - x) - abs(tree[q[i]]));
        ans = max(
            ans, sum + abs(get(t) - get(t - 1) + x) - abs(get(t) - get(t - 1)) +
                     abs(get(t + 1) - get(t) - x) - abs(get(t + 1) - get(t)));
        tot = 0;
        ask(1, n, t + 2, r + 1, 1);
        for (long long i = 1; i <= tot; i++)
          ans = max(ans, sum + x + abs(tree[q[i]] - x) - abs(tree[q[i]]));
      } else {
        tot = 0;
        if (ggg(l) >= 0)
          ask(1, n, l + 1, r + 1, 1);
        else
          ask(1, n, l, r, 1);
        for (long long i = 1; i <= tot; i++)
          ans = max(ans, sum + x + abs(tree[q[i]] - x) - abs(tree[q[i]]));
      }
      writeln(ans);
    }
  }
}

```