#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
inline int readint() {
  int res = 0;
  char c = 0;
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) res = res * 10 + c - '0', c = getchar();
  return res;
}
int n, q;
long long a[MAXN];
struct Line {
  long long k, b;
  Line(long long x = 0, long long y = 0, long long m = 0) {
    k = m, b = y - m * x;
  }
  bool operator<(const Line t) const { return b < t.b; }
};
inline long long calc(Line a, int x) { return a.k * x + a.b; }
struct Node {
  long long lazy, num;
  Line l[6];
} t[MAXN << 2];
inline void pushdown(int id) {
  t[id << 1].lazy += t[id].lazy;
  t[id << 1 | 1].lazy += t[id].lazy;
  t[id].lazy = 0;
}
inline void pushup(int id) {
  for (int i = 1; i <= 5; i++)
    t[id].l[i] = max(t[id << 1].l[i], t[id << 1 | 1].l[i]);
}
inline void build(int id, int l) {
  if (l == 1 || l == n) {
    long long f = l == 1 ? a[1] - a[2] : a[n] - a[n - 1];
    t[id].l[1] = Line(0, -(1ll << 62), -2);
    t[id].l[2] = Line(-f, -abs(f), -1);
    t[id].l[3] = Line(0, -(1ll << 62), 0);
    t[id].l[4] = Line(-f, -abs(f), 1);
    t[id].l[5] = Line(0, -(1ll << 62), 2);
  } else {
    long long f1 = a[l] - a[l - 1], f2 = a[l + 1] - a[l];
    long long left = min(-f1, f2), right = max(-f1, f2);
    t[id].l[1] = Line(left, abs(f1 + f2) - abs(f1) - abs(f2), -2);
    t[id].l[2] = Line(0, -(1ll << 62), -1);
    t[id].l[3] = Line(0, abs(f1 + f2) - abs(f1) - abs(f2), 0);
    t[id].l[4] = Line(0, -(1ll << 62), 1);
    t[id].l[5] = Line(right, abs(f1 + f2) - abs(f1) - abs(f2), 2);
  }
}
inline void buildTree(int id, int l, int r) {
  t[id].lazy = 0;
  if (l == r) {
    t[id].num = a[l], build(id, l);
    return;
  }
  int mid = (l + r) >> 1;
  buildTree(id << 1, l, mid), buildTree(id << 1 | 1, mid + 1, r);
  pushup(id);
}
inline void add(int id, int ql, int qr, int l, int r, long long d) {
  if (ql == l && qr == r) {
    t[id].lazy += d;
    return;
  }
  pushdown(id);
  int mid = (ql + qr) >> 1;
  if (r <= mid)
    add(id << 1, ql, mid, l, r, d);
  else if (l > mid)
    add(id << 1 | 1, mid + 1, qr, l, r, d);
  else
    add(id << 1, ql, mid, l, mid, d),
        add(id << 1 | 1, mid + 1, qr, mid + 1, r, d);
  pushup(id);
}
inline long long queryVal(int id, int ql, int qr, int pos) {
  if (ql == pos && qr == pos) return t[id].num + t[id].lazy;
  pushdown(id);
  int mid = (ql + qr) >> 1;
  if (pos <= mid)
    return queryVal(id << 1, ql, mid, pos);
  else
    return queryVal(id << 1 | 1, mid + 1, qr, pos);
}
inline void rebuild(int id, int ql, int qr, int pos) {
  if (ql == pos && qr == pos) {
    a[pos] = queryVal(1, 1, n, pos);
    if (pos > 1) a[pos - 1] = queryVal(1, 1, n, pos - 1);
    if (pos < n) a[pos + 1] = queryVal(1, 1, n, pos + 1);
    build(id, pos);
    return;
  }
  pushdown(id);
  int mid = (ql + qr) >> 1;
  if (pos <= mid)
    rebuild(id << 1, ql, mid, pos);
  else
    rebuild(id << 1 | 1, mid + 1, qr, pos);
  pushup(id);
}
inline long long query(int id, int ql, int qr, int l, int r, int x) {
  if (ql == l && qr == r) {
    long long res = -(1ll << 62);
    for (int i = 1; i <= 5; i++) res = max(res, calc(t[id].l[i], x));
    return res;
  }
  pushdown(id);
  int mid = (ql + qr) >> 1;
  if (r <= mid)
    return query(id << 1, ql, mid, l, r, x);
  else if (l > mid)
    return query(id << 1 | 1, mid + 1, qr, l, r, x);
  else
    return max(query(id << 1, ql, mid, l, mid, x),
               query(id << 1 | 1, mid + 1, qr, mid + 1, r, x));
}
int main() {
  n = readint();
  long long now = 0;
  for (int i = 1; i <= n; i++)
    a[i] = readint(), now += i > 1 ? abs(a[i] - a[i - 1]) : 0;
  buildTree(1, 1, n);
  q = readint();
  int op, l, r, x;
  while (q--) {
    op = readint(), l = readint(), r = readint(), x = readint();
    if (op == 1)
      printf("%lld\n", query(1, 1, n, l, r, x) + now);
    else {
      if (l > 1) {
        a[l] = queryVal(1, 1, n, l), a[l - 1] = queryVal(1, 1, n, l - 1);
        now += abs(a[l] - a[l - 1] + x) - abs(a[l] - a[l - 1]);
      }
      if (r < n) {
        a[r] = queryVal(1, 1, n, r), a[r + 1] = queryVal(1, 1, n, r + 1);
        now += abs(a[r] - a[r + 1] + x) - abs(a[r] - a[r + 1]);
      }
      add(1, 1, n, l, r, x);
      if (l > 1) rebuild(1, 1, n, l), rebuild(1, 1, n, l - 1);
      if (r < n) rebuild(1, 1, n, r), rebuild(1, 1, n, r + 1);
    }
  }
  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 int MAXN = 100005;
inline int readint() {
  int res = 0;
  char c = 0;
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) res = res * 10 + c - '0', c = getchar();
  return res;
}
int n, q;
long long a[MAXN];
struct Line {
  long long k, b;
  Line(long long x = 0, long long y = 0, long long m = 0) {
    k = m, b = y - m * x;
  }
  bool operator<(const Line t) const { return b < t.b; }
};
inline long long calc(Line a, int x) { return a.k * x + a.b; }
struct Node {
  long long lazy, num;
  Line l[6];
} t[MAXN << 2];
inline void pushdown(int id) {
  t[id << 1].lazy += t[id].lazy;
  t[id << 1 | 1].lazy += t[id].lazy;
  t[id].lazy = 0;
}
inline void pushup(int id) {
  for (int i = 1; i <= 5; i++)
    t[id].l[i] = max(t[id << 1].l[i], t[id << 1 | 1].l[i]);
}
inline void build(int id, int l) {
  if (l == 1 || l == n) {
    long long f = l == 1 ? a[1] - a[2] : a[n] - a[n - 1];
    t[id].l[1] = Line(0, -(1ll << 62), -2);
    t[id].l[2] = Line(-f, -abs(f), -1);
    t[id].l[3] = Line(0, -(1ll << 62), 0);
    t[id].l[4] = Line(-f, -abs(f), 1);
    t[id].l[5] = Line(0, -(1ll << 62), 2);
  } else {
    long long f1 = a[l] - a[l - 1], f2 = a[l + 1] - a[l];
    long long left = min(-f1, f2), right = max(-f1, f2);
    t[id].l[1] = Line(left, abs(f1 + f2) - abs(f1) - abs(f2), -2);
    t[id].l[2] = Line(0, -(1ll << 62), -1);
    t[id].l[3] = Line(0, abs(f1 + f2) - abs(f1) - abs(f2), 0);
    t[id].l[4] = Line(0, -(1ll << 62), 1);
    t[id].l[5] = Line(right, abs(f1 + f2) - abs(f1) - abs(f2), 2);
  }
}
inline void buildTree(int id, int l, int r) {
  t[id].lazy = 0;
  if (l == r) {
    t[id].num = a[l], build(id, l);
    return;
  }
  int mid = (l + r) >> 1;
  buildTree(id << 1, l, mid), buildTree(id << 1 | 1, mid + 1, r);
  pushup(id);
}
inline void add(int id, int ql, int qr, int l, int r, long long d) {
  if (ql == l && qr == r) {
    t[id].lazy += d;
    return;
  }
  pushdown(id);
  int mid = (ql + qr) >> 1;
  if (r <= mid)
    add(id << 1, ql, mid, l, r, d);
  else if (l > mid)
    add(id << 1 | 1, mid + 1, qr, l, r, d);
  else
    add(id << 1, ql, mid, l, mid, d),
        add(id << 1 | 1, mid + 1, qr, mid + 1, r, d);
  pushup(id);
}
inline long long queryVal(int id, int ql, int qr, int pos) {
  if (ql == pos && qr == pos) return t[id].num + t[id].lazy;
  pushdown(id);
  int mid = (ql + qr) >> 1;
  if (pos <= mid)
    return queryVal(id << 1, ql, mid, pos);
  else
    return queryVal(id << 1 | 1, mid + 1, qr, pos);
}
inline void rebuild(int id, int ql, int qr, int pos) {
  if (ql == pos && qr == pos) {
    a[pos] = queryVal(1, 1, n, pos);
    if (pos > 1) a[pos - 1] = queryVal(1, 1, n, pos - 1);
    if (pos < n) a[pos + 1] = queryVal(1, 1, n, pos + 1);
    build(id, pos);
    return;
  }
  pushdown(id);
  int mid = (ql + qr) >> 1;
  if (pos <= mid)
    rebuild(id << 1, ql, mid, pos);
  else
    rebuild(id << 1 | 1, mid + 1, qr, pos);
  pushup(id);
}
inline long long query(int id, int ql, int qr, int l, int r, int x) {
  if (ql == l && qr == r) {
    long long res = -(1ll << 62);
    for (int i = 1; i <= 5; i++) res = max(res, calc(t[id].l[i], x));
    return res;
  }
  pushdown(id);
  int mid = (ql + qr) >> 1;
  if (r <= mid)
    return query(id << 1, ql, mid, l, r, x);
  else if (l > mid)
    return query(id << 1 | 1, mid + 1, qr, l, r, x);
  else
    return max(query(id << 1, ql, mid, l, mid, x),
               query(id << 1 | 1, mid + 1, qr, mid + 1, r, x));
}
int main() {
  n = readint();
  long long now = 0;
  for (int i = 1; i <= n; i++)
    a[i] = readint(), now += i > 1 ? abs(a[i] - a[i - 1]) : 0;
  buildTree(1, 1, n);
  q = readint();
  int op, l, r, x;
  while (q--) {
    op = readint(), l = readint(), r = readint(), x = readint();
    if (op == 1)
      printf("%lld\n", query(1, 1, n, l, r, x) + now);
    else {
      if (l > 1) {
        a[l] = queryVal(1, 1, n, l), a[l - 1] = queryVal(1, 1, n, l - 1);
        now += abs(a[l] - a[l - 1] + x) - abs(a[l] - a[l - 1]);
      }
      if (r < n) {
        a[r] = queryVal(1, 1, n, r), a[r + 1] = queryVal(1, 1, n, r + 1);
        now += abs(a[r] - a[r + 1] + x) - abs(a[r] - a[r + 1]);
      }
      add(1, 1, n, l, r, x);
      if (l > 1) rebuild(1, 1, n, l), rebuild(1, 1, n, l - 1);
      if (r < n) rebuild(1, 1, n, r), rebuild(1, 1, n, r + 1);
    }
  }
  return 0;
}

```