#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
template <class T>
bool umin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool umax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
long long arr[100009];
int n;
set<int> one, two;
const long long J = 1e18;
struct tree {
  tree() { memset(lazy, 0, sizeof lazy); }
  long long lazy[100009 << 2];
  long long tap(int p, int nd, int x, int y) {
    if (x == y) return lazy[nd];
    lazy[nd << 1] += lazy[nd];
    lazy[nd << 1 | 1] += lazy[nd];
    lazy[nd] = 0;
    int mid = (x + y) >> 1;
    if (p <= mid) return tap(p, nd << 1, x, mid);
    return tap(p, nd << 1 | 1, mid + 1, y);
  }
  void upd(int p, long long v, int nd, int x, int y) {
    if (x == y) {
      lazy[nd] = v;
      return;
    }
    lazy[nd << 1] += lazy[nd];
    lazy[nd << 1 | 1] += lazy[nd];
    lazy[nd] = 0;
    int mid = (x + y) >> 1;
    if (p <= mid)
      upd(p, v, nd << 1, x, mid);
    else
      upd(p, v, nd << 1 | 1, mid + 1, y);
  }
  void inc(int l, int r, long long v, int nd, int x, int y) {
    if (l > y or x > r) return;
    if (l <= x and y <= r) {
      lazy[nd] += v;
      return;
    }
    lazy[nd << 1] += lazy[nd];
    lazy[nd << 1 | 1] += lazy[nd];
    lazy[nd] = 0;
    int mid = (x + y) >> 1;
    inc(l, r, v, nd << 1, x, mid);
    inc(l, r, v, nd << 1 | 1, mid + 1, y);
  }
} A, B, C;
struct agach {
  long long s[100009 << 2];
  void build(int nd, int x, int y) {
    s[nd] = J;
    if (x == y) return;
    int mid = (x + y) >> 1;
    build(nd << 1, x, mid);
    build(nd << 1 | 1, mid + 1, y);
  }
  void upd(int p, long long v, int nd, int x, int y) {
    if (x == y) {
      s[nd] = v;
      return;
    }
    int mid = (x + y) >> 1;
    if (p <= mid)
      upd(p, v, nd << 1, x, mid);
    else
      upd(p, v, nd << 1 | 1, mid + 1, y);
    s[nd] = min(s[nd << 1], s[nd << 1 | 1]);
  }
  long long tap(int l, int r, int nd, int x, int y) {
    if (l > y or x > r) return J;
    if (l <= x and y <= r) return s[nd];
    int mid = (x + y) >> 1;
    return min(tap(l, r, nd << 1, x, mid), tap(l, r, nd << 1 | 1, mid + 1, y));
  }
} CA;
void add(int x) {
  long long a = A.tap(x, 1, 1, n);
  long long b = B.tap(x, 1, 1, n);
  long long c = C.tap(x, 1, 1, n);
  if (a >= b and a >= c) one.insert(x);
  if (a < b and a < c) two.insert(x);
}
void remove(int x) {
  int a = A.tap(x, 1, 1, n);
  int b = B.tap(x, 1, 1, n);
  int c = B.tap(x, 1, 1, n);
  if (a >= b and a >= c) one.erase(x);
  if (a < b and a < c) two.erase(x);
}
int main() {
  scanf("%d", &n);
  CA.build(1, 1, n);
  for (int i = 1; i <= n; i++)
    scanf("%lld", arr + i), A.upd(i, arr[i], 1, 1, n);
  long long ans = 0;
  for (int i = 1; i < n; i++) ans += abs(arr[i] - arr[i + 1]);
  for (int i = 2; i < n; i++) {
    B.upd(i, min(arr[i + 1], arr[i - 1]), 1, 1, n);
    C.upd(i, max(arr[i + 1], arr[i - 1]), 1, 1, n);
    CA.upd(i, max(arr[i + 1], arr[i - 1]) - arr[i], 1, 1, n);
    add(i);
  }
  int q;
  scanf("%d", &q);
  while (q--) {
    int t, l, r, x;
    scanf("%d%d%d%d", &t, &l, &r, &x);
    if (t == 1) {
      if (one.size() > 0 and one.lower_bound(l) != one.end() and
          *(one.lower_bound(l)) <= r)
        printf("%lld\n", ans + x * 2LL);
      else {
        long long res = -J;
        if (two.size() != 0 and two.lower_bound(l) != two.end() and
            *two.lower_bound(l) <= r) {
          int pos = *two.lower_bound(l);
          if (l < pos)
            umax(res, 2LL * max(0LL, x - CA.tap(l, pos - 1, 1, 1, n)));
          if (pos < r)
            umax(res, 2LL * max(0LL, x - CA.tap(pos + 1, r, 1, 1, n)));
          umax(res,
               2LL * max(0LL, x - (C.tap(pos, 1, 1, n) - A.tap(pos, 1, 1, n))) -
                   2LL *
                       min(B.tap(pos, 1, 1, n) - A.tap(pos, 1, 1, n), x * 1LL));
        } else {
          umax(res, 2LL * max(0LL, x - CA.tap(l, r, 1, 1, n)));
        }
        printf("%lld\n", res + ans);
      }
    } else {
      long long a = A.tap(l - 1, 1, 1, n), b = A.tap(l, 1, 1, n);
      long long c = A.tap(r, 1, 1, n), d = A.tap(r + 1, 1, 1, n);
      ans -= abs(a - b);
      ans -= abs(c - d);
      if (l > 2) remove(l - 1);
      if (r + 2 <= n) remove(r + 1);
      if (l == r)
        remove(l);
      else
        remove(l), remove(r);
      A.inc(l, r, x, 1, 1, n);
      B.inc(l + 1, r - 1, x, 1, 1, n);
      C.inc(l + 1, r - 1, x, 1, 1, n);
      b += x;
      c += x;
      if (l > 2) {
        long long e = A.tap(l - 2, 1, 1, n);
        B.upd(l - 1, min(e, b), 1, 1, n);
        C.upd(l - 1, max(e, b), 1, 1, n);
        CA.upd(l - 1, max(e, b) - a, 1, 1, n);
        add(l - 1);
      }
      if (r + 2 <= n) {
        long long e = A.tap(r + 2, 1, 1, n);
        B.upd(r + 1, min(c, e), 1, 1, n);
        C.upd(r + 1, max(c, e), 1, 1, n);
        CA.upd(r + 1, max(c, e) - d, 1, 1, n);
        add(r + 1);
      }
      if (l == r) {
        long long e = A.tap(l + 1, 1, 1, n);
        B.upd(l, min(a, e), 1, 1, n);
        C.upd(l, max(a, e), 1, 1, n);
        CA.upd(l, max(a, e) - b, 1, 1, n);
        add(l);
      } else {
        long long e = A.tap(l + 1, 1, 1, n);
        B.upd(l, min(a, e), 1, 1, n);
        C.upd(l, max(a, e), 1, 1, n);
        CA.upd(l, max(a, e) - b, 1, 1, n);
        add(l);
        e = A.tap(r - 1, 1, 1, n);
        B.upd(r, min(e, d), 1, 1, n);
        C.upd(r, max(e, d), 1, 1, n);
        CA.upd(r, max(e, d) - c, 1, 1, n);
        add(r);
      }
      ans += abs(a - b);
      ans += abs(c - d);
    }
  }
  return 0;
}

### Prompt

In Cpp, your task is to solve 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>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
template <class T>
bool umin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool umax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
long long arr[100009];
int n;
set<int> one, two;
const long long J = 1e18;
struct tree {
  tree() { memset(lazy, 0, sizeof lazy); }
  long long lazy[100009 << 2];
  long long tap(int p, int nd, int x, int y) {
    if (x == y) return lazy[nd];
    lazy[nd << 1] += lazy[nd];
    lazy[nd << 1 | 1] += lazy[nd];
    lazy[nd] = 0;
    int mid = (x + y) >> 1;
    if (p <= mid) return tap(p, nd << 1, x, mid);
    return tap(p, nd << 1 | 1, mid + 1, y);
  }
  void upd(int p, long long v, int nd, int x, int y) {
    if (x == y) {
      lazy[nd] = v;
      return;
    }
    lazy[nd << 1] += lazy[nd];
    lazy[nd << 1 | 1] += lazy[nd];
    lazy[nd] = 0;
    int mid = (x + y) >> 1;
    if (p <= mid)
      upd(p, v, nd << 1, x, mid);
    else
      upd(p, v, nd << 1 | 1, mid + 1, y);
  }
  void inc(int l, int r, long long v, int nd, int x, int y) {
    if (l > y or x > r) return;
    if (l <= x and y <= r) {
      lazy[nd] += v;
      return;
    }
    lazy[nd << 1] += lazy[nd];
    lazy[nd << 1 | 1] += lazy[nd];
    lazy[nd] = 0;
    int mid = (x + y) >> 1;
    inc(l, r, v, nd << 1, x, mid);
    inc(l, r, v, nd << 1 | 1, mid + 1, y);
  }
} A, B, C;
struct agach {
  long long s[100009 << 2];
  void build(int nd, int x, int y) {
    s[nd] = J;
    if (x == y) return;
    int mid = (x + y) >> 1;
    build(nd << 1, x, mid);
    build(nd << 1 | 1, mid + 1, y);
  }
  void upd(int p, long long v, int nd, int x, int y) {
    if (x == y) {
      s[nd] = v;
      return;
    }
    int mid = (x + y) >> 1;
    if (p <= mid)
      upd(p, v, nd << 1, x, mid);
    else
      upd(p, v, nd << 1 | 1, mid + 1, y);
    s[nd] = min(s[nd << 1], s[nd << 1 | 1]);
  }
  long long tap(int l, int r, int nd, int x, int y) {
    if (l > y or x > r) return J;
    if (l <= x and y <= r) return s[nd];
    int mid = (x + y) >> 1;
    return min(tap(l, r, nd << 1, x, mid), tap(l, r, nd << 1 | 1, mid + 1, y));
  }
} CA;
void add(int x) {
  long long a = A.tap(x, 1, 1, n);
  long long b = B.tap(x, 1, 1, n);
  long long c = C.tap(x, 1, 1, n);
  if (a >= b and a >= c) one.insert(x);
  if (a < b and a < c) two.insert(x);
}
void remove(int x) {
  int a = A.tap(x, 1, 1, n);
  int b = B.tap(x, 1, 1, n);
  int c = B.tap(x, 1, 1, n);
  if (a >= b and a >= c) one.erase(x);
  if (a < b and a < c) two.erase(x);
}
int main() {
  scanf("%d", &n);
  CA.build(1, 1, n);
  for (int i = 1; i <= n; i++)
    scanf("%lld", arr + i), A.upd(i, arr[i], 1, 1, n);
  long long ans = 0;
  for (int i = 1; i < n; i++) ans += abs(arr[i] - arr[i + 1]);
  for (int i = 2; i < n; i++) {
    B.upd(i, min(arr[i + 1], arr[i - 1]), 1, 1, n);
    C.upd(i, max(arr[i + 1], arr[i - 1]), 1, 1, n);
    CA.upd(i, max(arr[i + 1], arr[i - 1]) - arr[i], 1, 1, n);
    add(i);
  }
  int q;
  scanf("%d", &q);
  while (q--) {
    int t, l, r, x;
    scanf("%d%d%d%d", &t, &l, &r, &x);
    if (t == 1) {
      if (one.size() > 0 and one.lower_bound(l) != one.end() and
          *(one.lower_bound(l)) <= r)
        printf("%lld\n", ans + x * 2LL);
      else {
        long long res = -J;
        if (two.size() != 0 and two.lower_bound(l) != two.end() and
            *two.lower_bound(l) <= r) {
          int pos = *two.lower_bound(l);
          if (l < pos)
            umax(res, 2LL * max(0LL, x - CA.tap(l, pos - 1, 1, 1, n)));
          if (pos < r)
            umax(res, 2LL * max(0LL, x - CA.tap(pos + 1, r, 1, 1, n)));
          umax(res,
               2LL * max(0LL, x - (C.tap(pos, 1, 1, n) - A.tap(pos, 1, 1, n))) -
                   2LL *
                       min(B.tap(pos, 1, 1, n) - A.tap(pos, 1, 1, n), x * 1LL));
        } else {
          umax(res, 2LL * max(0LL, x - CA.tap(l, r, 1, 1, n)));
        }
        printf("%lld\n", res + ans);
      }
    } else {
      long long a = A.tap(l - 1, 1, 1, n), b = A.tap(l, 1, 1, n);
      long long c = A.tap(r, 1, 1, n), d = A.tap(r + 1, 1, 1, n);
      ans -= abs(a - b);
      ans -= abs(c - d);
      if (l > 2) remove(l - 1);
      if (r + 2 <= n) remove(r + 1);
      if (l == r)
        remove(l);
      else
        remove(l), remove(r);
      A.inc(l, r, x, 1, 1, n);
      B.inc(l + 1, r - 1, x, 1, 1, n);
      C.inc(l + 1, r - 1, x, 1, 1, n);
      b += x;
      c += x;
      if (l > 2) {
        long long e = A.tap(l - 2, 1, 1, n);
        B.upd(l - 1, min(e, b), 1, 1, n);
        C.upd(l - 1, max(e, b), 1, 1, n);
        CA.upd(l - 1, max(e, b) - a, 1, 1, n);
        add(l - 1);
      }
      if (r + 2 <= n) {
        long long e = A.tap(r + 2, 1, 1, n);
        B.upd(r + 1, min(c, e), 1, 1, n);
        C.upd(r + 1, max(c, e), 1, 1, n);
        CA.upd(r + 1, max(c, e) - d, 1, 1, n);
        add(r + 1);
      }
      if (l == r) {
        long long e = A.tap(l + 1, 1, 1, n);
        B.upd(l, min(a, e), 1, 1, n);
        C.upd(l, max(a, e), 1, 1, n);
        CA.upd(l, max(a, e) - b, 1, 1, n);
        add(l);
      } else {
        long long e = A.tap(l + 1, 1, 1, n);
        B.upd(l, min(a, e), 1, 1, n);
        C.upd(l, max(a, e), 1, 1, n);
        CA.upd(l, max(a, e) - b, 1, 1, n);
        add(l);
        e = A.tap(r - 1, 1, 1, n);
        B.upd(r, min(e, d), 1, 1, n);
        C.upd(r, max(e, d), 1, 1, n);
        CA.upd(r, max(e, d) - c, 1, 1, n);
        add(r);
      }
      ans += abs(a - b);
      ans += abs(c - d);
    }
  }
  return 0;
}

```