#include <bits/stdc++.h>
using namespace std;
const double pi = 3.1415926535897932384626433832795;
const double eps = 1e-12;
const int INF = 1 << 30;
const long long LINF = 1LL << 62;
const int BUFFER_SZ = 1 << 20;
char BUFFER[BUFFER_SZ];
int gi() {
  int x;
  scanf("%d", &x);
  return x;
}
long long gll() {
  long long x;
  scanf("%lld", &x);
  return x;
}
vector<int> gvi(int n) {
  vector<int> a;
  while (n-- > 0) a.push_back(gi());
  return a;
}
string gs() {
  scanf("%s", BUFFER);
  return string(BUFFER);
}
long long randl() {
  return abs(1ll * rand() * rand() * rand() * rand() * rand() * rand());
}
template <class T>
void print(vector<T> &x, string format) {
  format += "%c";
  for (int i = 0; i < x.size(); ++i)
    printf(format.c_str(), x[i], i + 1 == x.size() ? '\n' : ' ');
}
const int SIZE = 110001;
struct tnode {
  long long lv, rv;
  long long best0;
  long long sum;
  tnode() : tnode(0) {}
  tnode(int x) : lv(x), rv(x), best0(LINF), sum(abs(x)) {}
};
tnode T[SIZE * 4];
long long A[111111];
void update(tnode &r, tnode &a, tnode &b) {
  long long m1 = a.rv;
  long long m2 = b.lv;
  long long b0 = (m1 < 0 && m2 > 0) ? -m1 + m2 : max(0ll, max(-m1, m2));
  r.lv = a.lv;
  r.rv = b.rv;
  r.best0 = min(b0, min(a.best0, b.best0));
  r.sum = a.sum + b.sum;
}
void build(int v, int l, int r) {
  if (l == r) {
    T[v] = tnode(A[l]);
  } else {
    int m = (l + r) >> 1;
    build(v << 1, l, m);
    build(v << 1 | 1, m + 1, r);
    update(T[v], T[v << 1], T[v << 1 | 1]);
  }
}
tnode getmin(int v, int tl, int tr, int l, int r) {
  if (tl == l && tr == r) return T[v];
  int m = (tl + tr) >> 1;
  if (l <= m && r > m) {
    tnode a = getmin(v << 1, tl, m, l, min(r, m));
    tnode b = getmin(v << 1 | 1, m + 1, tr, max(l, m + 1), r);
    tnode res;
    update(res, a, b);
    return res;
  } else if (l <= m) {
    return getmin(v << 1, tl, m, l, min(r, m));
  } else if (r > m) {
    return getmin(v << 1 | 1, m + 1, tr, max(l, m + 1), r);
  }
}
void add(int v, int tl, int tr, int p, int x) {
  if (tl == tr) {
    A[tl] += x;
    T[v].sum -= abs(T[v].lv);
    T[v].lv += x;
    T[v].rv += x;
    T[v].sum += abs(T[v].lv);
    return;
  }
  int m = (tl + tr) >> 1;
  if (p <= m) add(v << 1, tl, m, p, x);
  if (p > m) add(v << 1 | 1, m + 1, tr, p, x);
  update(T[v], T[v << 1], T[v << 1 | 1]);
}
void view(int v, int tl, int tr, string tab = "") {
  int m = (tl + tr) >> 1;
  if (tl != tr) {
    view(v << 1, tl, m, tab + "    ");
  }
  printf("%s[%lld] vl = %lld, vr = %lld, b0 = %lld\n", tab.c_str(), T[v].sum,
         T[v].lv, T[v].rv, T[v].best0);
  if (tl != tr) {
    view(v << 1 | 1, m + 1, tr, tab + "    ");
  }
}
void solve() {
  int n = gi();
  for (int i = 0; i < n; ++i) {
    A[i] = gi();
  }
  for (int i = 0; i < n - 1; ++i) A[i] = A[i + 1] - A[i];
  int N = n - 1;
  build(1, 0, N - 1);
  int m = gi();
  for (int i = 0; i < m; ++i) {
    int o = gi();
    int l = gi() - 1;
    int r = gi() - 1;
    if (l > r) swap(l, r);
    long long x = gi();
    if (o == 1) {
      if (l == r) {
        --l;
        long long s = T[1].sum;
        if (l >= 0) {
          s -= abs(A[l]);
          A[l] += x;
          s += abs(A[l]);
          A[l] -= x;
        }
        if (r <= N - 1) {
          s -= abs(A[r]);
          A[r] -= x;
          s += abs(A[r]);
          A[r] += x;
        }
        printf("%lld\n", s);
      } else {
        int L = max(0, l - 1);
        int R = min(r, N - 1);
        tnode res = getmin(1, 0, N - 1, L, R);
        long long v1 = max(x * 2 - res.best0 * 2, 0ll);
        long long v2 = l != 0 ? -LINF : max(0ll, x - max(0ll, T[1].lv));
        long long v3 = r != N ? -LINF : max(0ll, x - max(0ll, -T[1].rv));
        long long ret = T[1].sum + max(v1, max(v2, v3));
        printf("%lld\n", ret);
      }
    } else {
      if (l > 0) add(1, 0, N - 1, l - 1, x);
      if (r < N) add(1, 0, N - 1, r, -x);
    }
  }
}
int main() {
  solve();
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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 double pi = 3.1415926535897932384626433832795;
const double eps = 1e-12;
const int INF = 1 << 30;
const long long LINF = 1LL << 62;
const int BUFFER_SZ = 1 << 20;
char BUFFER[BUFFER_SZ];
int gi() {
  int x;
  scanf("%d", &x);
  return x;
}
long long gll() {
  long long x;
  scanf("%lld", &x);
  return x;
}
vector<int> gvi(int n) {
  vector<int> a;
  while (n-- > 0) a.push_back(gi());
  return a;
}
string gs() {
  scanf("%s", BUFFER);
  return string(BUFFER);
}
long long randl() {
  return abs(1ll * rand() * rand() * rand() * rand() * rand() * rand());
}
template <class T>
void print(vector<T> &x, string format) {
  format += "%c";
  for (int i = 0; i < x.size(); ++i)
    printf(format.c_str(), x[i], i + 1 == x.size() ? '\n' : ' ');
}
const int SIZE = 110001;
struct tnode {
  long long lv, rv;
  long long best0;
  long long sum;
  tnode() : tnode(0) {}
  tnode(int x) : lv(x), rv(x), best0(LINF), sum(abs(x)) {}
};
tnode T[SIZE * 4];
long long A[111111];
void update(tnode &r, tnode &a, tnode &b) {
  long long m1 = a.rv;
  long long m2 = b.lv;
  long long b0 = (m1 < 0 && m2 > 0) ? -m1 + m2 : max(0ll, max(-m1, m2));
  r.lv = a.lv;
  r.rv = b.rv;
  r.best0 = min(b0, min(a.best0, b.best0));
  r.sum = a.sum + b.sum;
}
void build(int v, int l, int r) {
  if (l == r) {
    T[v] = tnode(A[l]);
  } else {
    int m = (l + r) >> 1;
    build(v << 1, l, m);
    build(v << 1 | 1, m + 1, r);
    update(T[v], T[v << 1], T[v << 1 | 1]);
  }
}
tnode getmin(int v, int tl, int tr, int l, int r) {
  if (tl == l && tr == r) return T[v];
  int m = (tl + tr) >> 1;
  if (l <= m && r > m) {
    tnode a = getmin(v << 1, tl, m, l, min(r, m));
    tnode b = getmin(v << 1 | 1, m + 1, tr, max(l, m + 1), r);
    tnode res;
    update(res, a, b);
    return res;
  } else if (l <= m) {
    return getmin(v << 1, tl, m, l, min(r, m));
  } else if (r > m) {
    return getmin(v << 1 | 1, m + 1, tr, max(l, m + 1), r);
  }
}
void add(int v, int tl, int tr, int p, int x) {
  if (tl == tr) {
    A[tl] += x;
    T[v].sum -= abs(T[v].lv);
    T[v].lv += x;
    T[v].rv += x;
    T[v].sum += abs(T[v].lv);
    return;
  }
  int m = (tl + tr) >> 1;
  if (p <= m) add(v << 1, tl, m, p, x);
  if (p > m) add(v << 1 | 1, m + 1, tr, p, x);
  update(T[v], T[v << 1], T[v << 1 | 1]);
}
void view(int v, int tl, int tr, string tab = "") {
  int m = (tl + tr) >> 1;
  if (tl != tr) {
    view(v << 1, tl, m, tab + "    ");
  }
  printf("%s[%lld] vl = %lld, vr = %lld, b0 = %lld\n", tab.c_str(), T[v].sum,
         T[v].lv, T[v].rv, T[v].best0);
  if (tl != tr) {
    view(v << 1 | 1, m + 1, tr, tab + "    ");
  }
}
void solve() {
  int n = gi();
  for (int i = 0; i < n; ++i) {
    A[i] = gi();
  }
  for (int i = 0; i < n - 1; ++i) A[i] = A[i + 1] - A[i];
  int N = n - 1;
  build(1, 0, N - 1);
  int m = gi();
  for (int i = 0; i < m; ++i) {
    int o = gi();
    int l = gi() - 1;
    int r = gi() - 1;
    if (l > r) swap(l, r);
    long long x = gi();
    if (o == 1) {
      if (l == r) {
        --l;
        long long s = T[1].sum;
        if (l >= 0) {
          s -= abs(A[l]);
          A[l] += x;
          s += abs(A[l]);
          A[l] -= x;
        }
        if (r <= N - 1) {
          s -= abs(A[r]);
          A[r] -= x;
          s += abs(A[r]);
          A[r] += x;
        }
        printf("%lld\n", s);
      } else {
        int L = max(0, l - 1);
        int R = min(r, N - 1);
        tnode res = getmin(1, 0, N - 1, L, R);
        long long v1 = max(x * 2 - res.best0 * 2, 0ll);
        long long v2 = l != 0 ? -LINF : max(0ll, x - max(0ll, T[1].lv));
        long long v3 = r != N ? -LINF : max(0ll, x - max(0ll, -T[1].rv));
        long long ret = T[1].sum + max(v1, max(v2, v3));
        printf("%lld\n", ret);
      }
    } else {
      if (l > 0) add(1, 0, N - 1, l - 1, x);
      if (r < N) add(1, 0, N - 1, r, -x);
    }
  }
}
int main() {
  solve();
  return 0;
}

```