#include <bits/stdc++.h>
using namespace std;
const int Maxn = 100010;
const long long inf = (1LL << 55);
long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
  return x * f;
}
int n, q;
long long s[Maxn], a[Maxn];
void Add(int x, long long y) {
  for (; x <= n; x += (x & -x)) s[x] += y;
}
long long Query(int x) {
  long long re = 0;
  for (; x; x -= (x & -x)) re += s[x];
  return re;
}
struct Seg {
  int l, r, lc, rc, pos;
  long long mn;
} tr[3][Maxn << 1];
int tot = 0;
void up(int o, int x) {
  int lc = tr[o][x].lc, rc = tr[o][x].rc;
  if (o < 2)
    tr[o][x].mn = min(tr[o][lc].mn, tr[o][rc].mn);
  else
    tr[o][x].pos = max(tr[o][lc].pos, tr[o][rc].pos);
}
void build(int o, int l, int r) {
  int t = ++tot;
  tr[o][t].l = l;
  tr[o][t].r = r;
  if (l == r) {
    if (o == 0) {
      if (a[l] >= a[l - 1])
        tr[o][t].mn = a[l + 1] - a[l];
      else
        tr[o][t].mn = inf;
    } else if (o == 1) {
      if (a[l] >= a[l + 1])
        tr[o][t].mn = a[l - 1] - a[l];
      else
        tr[o][t].mn = inf;
    } else {
      if (a[l] < a[l - 1] && a[l] < a[l + 1])
        tr[o][t].pos = l;
      else
        tr[o][t].pos = 0;
    }
    return;
  }
  int mid = l + r >> 1;
  tr[o][t].lc = tot + 1, build(o, l, mid);
  tr[o][t].rc = tot + 1, build(o, mid + 1, r);
  up(o, t);
}
long long query(int o, int x, int l, int r) {
  if (tr[o][x].l == l && tr[o][x].r == r) return tr[o][x].mn;
  int mid = tr[o][x].l + tr[o][x].r >> 1, lc = tr[o][x].lc, rc = tr[o][x].rc;
  if (r <= mid)
    return query(o, lc, l, r);
  else if (l > mid)
    return query(o, rc, l, r);
  else
    return min(query(o, lc, l, mid), query(o, rc, mid + 1, r));
}
void modify(int o, int x, int p, long long v) {
  if (tr[o][x].l == tr[o][x].r) {
    if (o < 2)
      tr[o][x].mn = v;
    else
      tr[o][x].pos = v;
    return;
  }
  int mid = tr[o][x].l + tr[o][x].r >> 1, lc = tr[o][x].lc, rc = tr[o][x].rc;
  if (p <= mid)
    modify(o, lc, p, v);
  else
    modify(o, rc, p, v);
  up(o, x);
}
int query_pos(int x, int l, int r) {
  if (tr[2][x].l == l && tr[2][x].r == r) return tr[2][x].pos;
  int mid = tr[2][x].l + tr[2][x].r >> 1, lc = tr[2][x].lc, rc = tr[2][x].rc;
  if (r <= mid)
    return query_pos(lc, l, r);
  else if (l > mid)
    return query_pos(rc, l, r);
  else
    return max(query_pos(lc, l, mid), query_pos(rc, mid + 1, r));
}
long long ans = 0;
void solve(int l, int r, long long x) {
  long long a, b, c, d, tmp = -inf, t1, t2, t3;
  if (l == 1) {
    l++;
    a = Query(1), b = Query(2);
    t1 = abs(a - b);
    t2 = abs((a + x) - b);
    tmp = max(tmp, ans - t1 + t2);
  }
  if (r == n) {
    r--;
    c = Query(n - 1), d = Query(n);
    t1 = abs(c - d);
    t2 = abs(c - (d + x));
    tmp = max(tmp, ans - t1 + t2);
  }
  t1 = query(0, 1, l, r);
  t2 = query(1, 1, l, r);
  if (t1 <= 0 || t2 <= 0) {
    printf("%lld\n", ans + (x << 1));
    return;
  }
  if (t1 != inf) {
    if (t1 >= x)
      tmp = max(tmp, ans);
    else
      tmp = max(tmp, ans + (x << 1) - (t1 << 1));
  }
  if (t2 != inf) {
    if (t2 >= x)
      tmp = max(tmp, ans);
    else
      tmp = max(tmp, ans + (x << 1) - (t2 << 1));
  }
  t3 = query_pos(1, l, r);
  if (t3) {
    a = Query(t3 - 1), b = Query(t3), c = Query(t3 + 1);
    tmp = max(tmp, ans - abs(a - b) - abs(b - c) + abs(a - (b + x)) +
                       abs((b + x) - c));
  }
  printf("%lld\n", tmp);
}
int main() {
  n = read();
  long long last = 0;
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    Add(i, a[i] - last);
    if (i > 1) ans += abs(last - a[i]);
    last = a[i];
  }
  tot = 0;
  build(0, 2, n - 1);
  tot = 0;
  build(1, 2, n - 1);
  tot = 0;
  build(2, 2, n - 1);
  q = read();
  for (int i = 1; i <= q; i++) {
    int op = read(), l = read(), r = read();
    long long x = read();
    if (op == 1) {
      if (l == r) {
        long long a, b = Query(l), c, t1 = 0, t2 = 0;
        if (l == 1)
          a = -1;
        else
          a = Query(l - 1);
        if (l == n)
          c = -1;
        else
          c = Query(l + 1);
        if (a != -1) t1 += abs(a - b), t2 += abs(a - (b + x));
        if (c != -1) t1 += abs(b - c), t2 += abs((b + x) - c);
        printf("%lld\n", ans - t1 + t2);
      } else
        solve(l, r, x);
    } else {
      long long a = -1, b = Query(l), c = Query(r), d = -1, e;
      if (l != 1) a = Query(l - 1);
      if (r != n) d = Query(r + 1);
      if (a != -1) {
        if (l != n) {
          e = Query(l + 1);
          if (b >= a) modify(0, 1, l, inf);
          if (b >= e) modify(1, 1, l, inf);
          if (b < a && b < e) modify(2, 1, l, 0);
          if (l != r) e += x;
          if (b + x >= a) modify(0, 1, l, e - (b + x));
          if (b + x >= e) modify(1, 1, l, a - (b + x));
          if (b + x < a && b + x < e) modify(2, 1, l, l);
        }
        if (l > 2) {
          e = Query(l - 2);
          if (a >= b) modify(1, 1, l - 1, inf);
          if (a < e && a < b) modify(2, 1, l - 1, 0);
          if (a >= e) modify(0, 1, l - 1, (b + x) - a);
          if (a >= b + x) modify(1, 1, l - 1, e - a);
          if (a < e && a < b + x) modify(2, 1, l - 1, l - 1);
        }
      }
      if (d != -1) {
        if (r != 1) {
          e = Query(r - 1);
          if (c >= e) modify(0, 1, r, inf);
          if (c >= d) modify(1, 1, r, inf);
          if (c < e && c < d) modify(2, 1, r, 0);
          if (l != r) e += x;
          if (c + x >= e) modify(0, 1, r, d - (c + x));
          if (c + x >= d) modify(1, 1, r, e - (c + x));
          if (c + x < e && c + x < d) modify(2, 1, r, r);
        }
        if (r < n - 1) {
          e = Query(r + 2);
          if (d >= c) modify(0, 1, r + 1, inf);
          if (d < c && d < e) modify(2, 1, r + 1, 0);
          if (d >= c + x) modify(0, 1, r + 1, e - d);
          if (d >= e) modify(1, 1, r + 1, (c + x) - d);
          if (d < c + x && d < e) modify(2, 1, r + 1, r + 1);
        }
      }
      if (a != -1) ans = ans - abs(a - b) + abs(a - (b + x));
      if (d != -1) ans = ans - abs(c - d) + abs((c + x) - d);
      Add(l, x);
      Add(r + 1, -x);
    }
  }
}

### 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;
const int Maxn = 100010;
const long long inf = (1LL << 55);
long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
  return x * f;
}
int n, q;
long long s[Maxn], a[Maxn];
void Add(int x, long long y) {
  for (; x <= n; x += (x & -x)) s[x] += y;
}
long long Query(int x) {
  long long re = 0;
  for (; x; x -= (x & -x)) re += s[x];
  return re;
}
struct Seg {
  int l, r, lc, rc, pos;
  long long mn;
} tr[3][Maxn << 1];
int tot = 0;
void up(int o, int x) {
  int lc = tr[o][x].lc, rc = tr[o][x].rc;
  if (o < 2)
    tr[o][x].mn = min(tr[o][lc].mn, tr[o][rc].mn);
  else
    tr[o][x].pos = max(tr[o][lc].pos, tr[o][rc].pos);
}
void build(int o, int l, int r) {
  int t = ++tot;
  tr[o][t].l = l;
  tr[o][t].r = r;
  if (l == r) {
    if (o == 0) {
      if (a[l] >= a[l - 1])
        tr[o][t].mn = a[l + 1] - a[l];
      else
        tr[o][t].mn = inf;
    } else if (o == 1) {
      if (a[l] >= a[l + 1])
        tr[o][t].mn = a[l - 1] - a[l];
      else
        tr[o][t].mn = inf;
    } else {
      if (a[l] < a[l - 1] && a[l] < a[l + 1])
        tr[o][t].pos = l;
      else
        tr[o][t].pos = 0;
    }
    return;
  }
  int mid = l + r >> 1;
  tr[o][t].lc = tot + 1, build(o, l, mid);
  tr[o][t].rc = tot + 1, build(o, mid + 1, r);
  up(o, t);
}
long long query(int o, int x, int l, int r) {
  if (tr[o][x].l == l && tr[o][x].r == r) return tr[o][x].mn;
  int mid = tr[o][x].l + tr[o][x].r >> 1, lc = tr[o][x].lc, rc = tr[o][x].rc;
  if (r <= mid)
    return query(o, lc, l, r);
  else if (l > mid)
    return query(o, rc, l, r);
  else
    return min(query(o, lc, l, mid), query(o, rc, mid + 1, r));
}
void modify(int o, int x, int p, long long v) {
  if (tr[o][x].l == tr[o][x].r) {
    if (o < 2)
      tr[o][x].mn = v;
    else
      tr[o][x].pos = v;
    return;
  }
  int mid = tr[o][x].l + tr[o][x].r >> 1, lc = tr[o][x].lc, rc = tr[o][x].rc;
  if (p <= mid)
    modify(o, lc, p, v);
  else
    modify(o, rc, p, v);
  up(o, x);
}
int query_pos(int x, int l, int r) {
  if (tr[2][x].l == l && tr[2][x].r == r) return tr[2][x].pos;
  int mid = tr[2][x].l + tr[2][x].r >> 1, lc = tr[2][x].lc, rc = tr[2][x].rc;
  if (r <= mid)
    return query_pos(lc, l, r);
  else if (l > mid)
    return query_pos(rc, l, r);
  else
    return max(query_pos(lc, l, mid), query_pos(rc, mid + 1, r));
}
long long ans = 0;
void solve(int l, int r, long long x) {
  long long a, b, c, d, tmp = -inf, t1, t2, t3;
  if (l == 1) {
    l++;
    a = Query(1), b = Query(2);
    t1 = abs(a - b);
    t2 = abs((a + x) - b);
    tmp = max(tmp, ans - t1 + t2);
  }
  if (r == n) {
    r--;
    c = Query(n - 1), d = Query(n);
    t1 = abs(c - d);
    t2 = abs(c - (d + x));
    tmp = max(tmp, ans - t1 + t2);
  }
  t1 = query(0, 1, l, r);
  t2 = query(1, 1, l, r);
  if (t1 <= 0 || t2 <= 0) {
    printf("%lld\n", ans + (x << 1));
    return;
  }
  if (t1 != inf) {
    if (t1 >= x)
      tmp = max(tmp, ans);
    else
      tmp = max(tmp, ans + (x << 1) - (t1 << 1));
  }
  if (t2 != inf) {
    if (t2 >= x)
      tmp = max(tmp, ans);
    else
      tmp = max(tmp, ans + (x << 1) - (t2 << 1));
  }
  t3 = query_pos(1, l, r);
  if (t3) {
    a = Query(t3 - 1), b = Query(t3), c = Query(t3 + 1);
    tmp = max(tmp, ans - abs(a - b) - abs(b - c) + abs(a - (b + x)) +
                       abs((b + x) - c));
  }
  printf("%lld\n", tmp);
}
int main() {
  n = read();
  long long last = 0;
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    Add(i, a[i] - last);
    if (i > 1) ans += abs(last - a[i]);
    last = a[i];
  }
  tot = 0;
  build(0, 2, n - 1);
  tot = 0;
  build(1, 2, n - 1);
  tot = 0;
  build(2, 2, n - 1);
  q = read();
  for (int i = 1; i <= q; i++) {
    int op = read(), l = read(), r = read();
    long long x = read();
    if (op == 1) {
      if (l == r) {
        long long a, b = Query(l), c, t1 = 0, t2 = 0;
        if (l == 1)
          a = -1;
        else
          a = Query(l - 1);
        if (l == n)
          c = -1;
        else
          c = Query(l + 1);
        if (a != -1) t1 += abs(a - b), t2 += abs(a - (b + x));
        if (c != -1) t1 += abs(b - c), t2 += abs((b + x) - c);
        printf("%lld\n", ans - t1 + t2);
      } else
        solve(l, r, x);
    } else {
      long long a = -1, b = Query(l), c = Query(r), d = -1, e;
      if (l != 1) a = Query(l - 1);
      if (r != n) d = Query(r + 1);
      if (a != -1) {
        if (l != n) {
          e = Query(l + 1);
          if (b >= a) modify(0, 1, l, inf);
          if (b >= e) modify(1, 1, l, inf);
          if (b < a && b < e) modify(2, 1, l, 0);
          if (l != r) e += x;
          if (b + x >= a) modify(0, 1, l, e - (b + x));
          if (b + x >= e) modify(1, 1, l, a - (b + x));
          if (b + x < a && b + x < e) modify(2, 1, l, l);
        }
        if (l > 2) {
          e = Query(l - 2);
          if (a >= b) modify(1, 1, l - 1, inf);
          if (a < e && a < b) modify(2, 1, l - 1, 0);
          if (a >= e) modify(0, 1, l - 1, (b + x) - a);
          if (a >= b + x) modify(1, 1, l - 1, e - a);
          if (a < e && a < b + x) modify(2, 1, l - 1, l - 1);
        }
      }
      if (d != -1) {
        if (r != 1) {
          e = Query(r - 1);
          if (c >= e) modify(0, 1, r, inf);
          if (c >= d) modify(1, 1, r, inf);
          if (c < e && c < d) modify(2, 1, r, 0);
          if (l != r) e += x;
          if (c + x >= e) modify(0, 1, r, d - (c + x));
          if (c + x >= d) modify(1, 1, r, e - (c + x));
          if (c + x < e && c + x < d) modify(2, 1, r, r);
        }
        if (r < n - 1) {
          e = Query(r + 2);
          if (d >= c) modify(0, 1, r + 1, inf);
          if (d < c && d < e) modify(2, 1, r + 1, 0);
          if (d >= c + x) modify(0, 1, r + 1, e - d);
          if (d >= e) modify(1, 1, r + 1, (c + x) - d);
          if (d < c + x && d < e) modify(2, 1, r + 1, r + 1);
        }
      }
      if (a != -1) ans = ans - abs(a - b) + abs(a - (b + x));
      if (d != -1) ans = ans - abs(c - d) + abs((c + x) - d);
      Add(l, x);
      Add(r + 1, -x);
    }
  }
}

```