#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, Q, a[N];
long long tt[N], ans;
void change(int x, int v) {
  for (; x <= n; x += x & (-x)) tt[x] += v;
}
long long ask(int x) {
  long long ans = 0;
  for (; x; x -= x & (-x)) ans += tt[x];
  return ans;
}
struct node {
  long long v1a, v1b, v2, v3;
} t[N * 4];
node operator+(node a, node b) {
  node ans;
  ans.v3 = a.v3 | b.v3;
  ans.v2 = min(a.v2, b.v2);
  ans.v1a = min(a.v1a, b.v1a);
  ans.v1b = min(a.v1b, b.v1b);
  return ans;
}
void build(int k, int l, int r) {
  if (l == r) {
    long long v1 = ask(l - 1), v2 = ask(l), v3 = ask(l + 1);
    if (v1 > v3) swap(v1, v3);
    if (v2 >= v3)
      t[k] = (node){1ll << 60, 1ll << 60, 1ll << 60, 1};
    else if (v2 < v1)
      t[k] = (node){v3 + v1 - v2 - v2, v1 - v2, 1ll << 60, 0};
    else
      t[k] = (node){1ll << 60, 1ll < 60, v3 - v2, 0};
    return;
  }
  int mid = (l + r) / 2;
  build(k * 2, l, mid);
  build(k * 2 + 1, mid + 1, r);
  t[k] = t[k * 2] + t[k * 2 + 1];
}
void change(int k, int l, int r, int p) {
  if (l == r) {
    long long v1 = ask(l - 1), v2 = ask(l), v3 = ask(l + 1);
    if (v1 > v3) swap(v1, v3);
    if (v2 >= v3)
      t[k] = (node){1ll << 60, 1ll << 60, 1ll << 60, 1};
    else if (v2 < v1)
      t[k] = (node){v3 + v1 - v2 - v2, v1 - v2, 1ll << 60, 0};
    else
      t[k] = (node){1ll << 60, 1ll < 60, v3 - v2, 0};
    return;
  }
  int mid = (l + r) / 2;
  if (p <= mid)
    change(k * 2, l, mid, p);
  else
    change(k * 2 + 1, mid + 1, r, p);
  t[k] = t[k * 2] + t[k * 2 + 1];
}
node ask(int k, int l, int r, int x, int y) {
  if (x <= l && r <= y) return t[k];
  int mid = (l + r) / 2;
  if (y <= mid) return ask(k * 2, l, mid, x, y);
  if (x > mid) return ask(k * 2 + 1, mid + 1, r, x, y);
  return ask(k * 2, l, mid, x, mid) + ask(k * 2 + 1, mid + 1, r, mid + 1, y);
}
void query(int x, int y, int v) {
  long long dif = -(1ll << 60);
  node tmp = ask(1, 2, n - 1, x, y);
  if (tmp.v3)
    dif = 2 * v;
  else {
    if (tmp.v2 != (1ll << 60)) dif = max(0ll, 2 * (v - tmp.v2));
    if (tmp.v1a != (1ll << 60))
      if (v <= tmp.v1b)
        dif = max(dif, 2ll * (-v));
      else
        dif = max(dif, 2 * max(v - tmp.v1a, -tmp.v1b));
  }
  printf("%lld\n", ans + dif);
}
void change(int x, int y, int v) {
  ans -= abs(ask(x) - ask(x - 1));
  ans -= abs(ask(y + 1) - ask(y));
  change(x, v);
  change(y + 1, -v);
  ans += abs(ask(x) - ask(x - 1));
  ans += abs(ask(y + 1) - ask(y));
  if (x != 2) change(1, 2, n - 1, x - 1);
  change(1, 2, n - 1, x);
  change(1, 2, n - 1, y);
  if (y != n - 1) change(1, 2, n - 1, y + 1);
}
int main() {
  scanf("%d", &n);
  for (int i = (int)(1); i <= (int)(n); i++) scanf("%d", &a[i]);
  for (int i = (int)(1); i <= (int)(n - 1); i++) ans += abs(a[i] - a[i + 1]);
  for (int i = (int)(1); i <= (int)(n); i++) change(i, a[i] - a[i - 1]);
  build(1, 2, n - 1);
  scanf("%d", &Q);
  while (Q--) {
    int tp, x, y, v;
    scanf("%d%d%d%d", &tp, &x, &y, &v);
    if (tp == 1)
      query(x, y, v);
    else
      change(x, y, v);
  }
}

### Prompt

Please create a solution in CPP 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>
using namespace std;
const int N = 100005;
int n, Q, a[N];
long long tt[N], ans;
void change(int x, int v) {
  for (; x <= n; x += x & (-x)) tt[x] += v;
}
long long ask(int x) {
  long long ans = 0;
  for (; x; x -= x & (-x)) ans += tt[x];
  return ans;
}
struct node {
  long long v1a, v1b, v2, v3;
} t[N * 4];
node operator+(node a, node b) {
  node ans;
  ans.v3 = a.v3 | b.v3;
  ans.v2 = min(a.v2, b.v2);
  ans.v1a = min(a.v1a, b.v1a);
  ans.v1b = min(a.v1b, b.v1b);
  return ans;
}
void build(int k, int l, int r) {
  if (l == r) {
    long long v1 = ask(l - 1), v2 = ask(l), v3 = ask(l + 1);
    if (v1 > v3) swap(v1, v3);
    if (v2 >= v3)
      t[k] = (node){1ll << 60, 1ll << 60, 1ll << 60, 1};
    else if (v2 < v1)
      t[k] = (node){v3 + v1 - v2 - v2, v1 - v2, 1ll << 60, 0};
    else
      t[k] = (node){1ll << 60, 1ll < 60, v3 - v2, 0};
    return;
  }
  int mid = (l + r) / 2;
  build(k * 2, l, mid);
  build(k * 2 + 1, mid + 1, r);
  t[k] = t[k * 2] + t[k * 2 + 1];
}
void change(int k, int l, int r, int p) {
  if (l == r) {
    long long v1 = ask(l - 1), v2 = ask(l), v3 = ask(l + 1);
    if (v1 > v3) swap(v1, v3);
    if (v2 >= v3)
      t[k] = (node){1ll << 60, 1ll << 60, 1ll << 60, 1};
    else if (v2 < v1)
      t[k] = (node){v3 + v1 - v2 - v2, v1 - v2, 1ll << 60, 0};
    else
      t[k] = (node){1ll << 60, 1ll < 60, v3 - v2, 0};
    return;
  }
  int mid = (l + r) / 2;
  if (p <= mid)
    change(k * 2, l, mid, p);
  else
    change(k * 2 + 1, mid + 1, r, p);
  t[k] = t[k * 2] + t[k * 2 + 1];
}
node ask(int k, int l, int r, int x, int y) {
  if (x <= l && r <= y) return t[k];
  int mid = (l + r) / 2;
  if (y <= mid) return ask(k * 2, l, mid, x, y);
  if (x > mid) return ask(k * 2 + 1, mid + 1, r, x, y);
  return ask(k * 2, l, mid, x, mid) + ask(k * 2 + 1, mid + 1, r, mid + 1, y);
}
void query(int x, int y, int v) {
  long long dif = -(1ll << 60);
  node tmp = ask(1, 2, n - 1, x, y);
  if (tmp.v3)
    dif = 2 * v;
  else {
    if (tmp.v2 != (1ll << 60)) dif = max(0ll, 2 * (v - tmp.v2));
    if (tmp.v1a != (1ll << 60))
      if (v <= tmp.v1b)
        dif = max(dif, 2ll * (-v));
      else
        dif = max(dif, 2 * max(v - tmp.v1a, -tmp.v1b));
  }
  printf("%lld\n", ans + dif);
}
void change(int x, int y, int v) {
  ans -= abs(ask(x) - ask(x - 1));
  ans -= abs(ask(y + 1) - ask(y));
  change(x, v);
  change(y + 1, -v);
  ans += abs(ask(x) - ask(x - 1));
  ans += abs(ask(y + 1) - ask(y));
  if (x != 2) change(1, 2, n - 1, x - 1);
  change(1, 2, n - 1, x);
  change(1, 2, n - 1, y);
  if (y != n - 1) change(1, 2, n - 1, y + 1);
}
int main() {
  scanf("%d", &n);
  for (int i = (int)(1); i <= (int)(n); i++) scanf("%d", &a[i]);
  for (int i = (int)(1); i <= (int)(n - 1); i++) ans += abs(a[i] - a[i + 1]);
  for (int i = (int)(1); i <= (int)(n); i++) change(i, a[i] - a[i - 1]);
  build(1, 2, n - 1);
  scanf("%d", &Q);
  while (Q--) {
    int tp, x, y, v;
    scanf("%d%d%d%d", &tp, &x, &y, &v);
    if (tp == 1)
      query(x, y, v);
    else
      change(x, y, v);
  }
}

```