#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <class T>
T ceil(T x, T y) {
  assert(y >= 1);
  return (x > 0 ? (x + y - 1) / y : x / y);
}
template <class T>
T floor(T x, T y) {
  assert(y >= 1);
  return (x > 0 ? x / y : (x - y + 1) / y);
}
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(long double &a) { cin >> a; }
void scan(string &a) { cin >> a; }
template <class T, class S>
void scan(pair<T, S> &p) {
  scan(p.first), scan(p.second);
}
template <class T>
void scan(vector<T> &a) {
  for (auto &i : a) scan(i);
}
template <class T>
void scan(T &a) {
  cin >> a;
}
void IN() {}
template <class Head, class... Tail>
void IN(Head &head, Tail &...tail) {
  scan(head);
  IN(tail...);
}
vi s_to_vi(string S, char first_char = 'a') {
  vi A(S.size());
  for (ll i = 0; (i) < (ll)(S.size()); ++(i)) {
    A[i] = S[i] - first_char;
  }
  return A;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &A) {
  os << A.first << " " << A.second;
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &A) {
  for (size_t i = 0; i < A.size(); i++) {
    if (i) os << " ";
    os << A[i];
  }
  return os;
}
void print() { cout << "\n"; }
template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
  cout << head;
  if (sizeof...(Tail)) cout << " ";
  print(forward<Tail>(tail)...);
}
const string YESNO[2] = {"NO", "YES"};
const string YesNo[2] = {"No", "Yes"};
const string yesno[2] = {"no", "yes"};
void YES(bool t = 1) { cout << YESNO[t] << endl; }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { cout << YesNo[t] << endl; }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { cout << yesno[t] << endl; }
void no(bool t = 1) { yes(!t); }
template <typename T>
vector<T> cumsum(vector<T> A) {
  ll N = A.size();
  vector<T> B(N + 1);
  B[0] = T(0);
  for (ll i = 0; (i) < (ll)(N); ++(i)) {
    B[i + 1] = B[i] + A[i];
  }
  return B;
}
vi bin_count(vi &A, ll size) {
  vi C(size);
  for (auto &&x : A) {
    ++C[x];
  }
  return C;
}
template <typename T>
vi argsort(vector<T> &A) {
  vi ids(A.size());
  iota(ids.begin(), ids.end(), 0);
  sort(ids.begin(), ids.end(),
       [&](ll i, ll j) { return make_pair(A[i], i) <= make_pair(A[j], j); });
  return ids;
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
  return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
  return (a > b ? a = b, 1 : 0);
}
template <typename T>
struct SegTree {
  using F = function<T(T, T)>;
  int N_;
  int N;
  F seg_f;
  T T_unit;
  vector<T> dat;
  SegTree(F f, T T_unit) : seg_f(f), T_unit(T_unit) {}
  void init(int n_) {
    N_ = n_;
    N = 1;
    while (N < n_) N <<= 1;
    dat.assign(N << 1, T_unit);
  }
  void build(const vector<T> &v) {
    init(v.size());
    for (ll i = 0; (i) < (ll)(N); ++(i)) dat[N + i] = v[i];
    for (ll i = (ll)(N)-1; (i) >= (ll)(1); --(i)) {
      dat[i] = seg_f(dat[i << 1 | 0], dat[i << 1 | 1]);
    }
  }
  void set_val(int i, T x) {
    dat[i += N] = x;
    while (i >>= 1) {
      dat[i] = seg_f(dat[i << 1 | 0], dat[i << 1 | 1]);
    }
  }
  T fold(int L, int R) {
    assert(L <= R);
    T vl = T_unit, vr = T_unit;
    L += N;
    R += N;
    while (L < R) {
      if (L & 1) vl = seg_f(vl, dat[L++]);
      if (R & 1) vr = seg_f(dat[--R], vr);
      L >>= 1;
      R >>= 1;
    }
    return seg_f(vl, vr);
  }
  template <typename C>
  int max_right(int s, C &check, T &acc, int k, int l, int r) {
    if (l + 1 == r) {
      acc = seg_f(acc, dat[k]);
      return check(acc) ? -1 : k - N;
    }
    int m = (l + r) >> 1;
    if (m <= s) return max_right(s, check, acc, (k << 1) | 1, m, r);
    if (s <= l and check(seg_f(acc, dat[k]))) {
      acc = seg_f(acc, dat[k]);
      return -1;
    }
    int vl = max_right(s, check, acc, (k << 1) | 0, l, m);
    if (~vl) return vl;
    return max_right(s, check, acc, (k << 1) | 1, m, r);
  }
  template <typename C>
  int max_right(int s, C &check) {
    assert(s < N and check(T_unit));
    if (check(fold(s, N_))) return N_;
    T acc = T_unit;
    return max_right(s, check, acc, 1, 0, N);
  }
};
const ll INF = 1LL << 60;
void solve() {
  ll N;
  IN(N);
  vector<ll> A(N);
  IN(A);
  ll Q;
  IN(Q);
  vi B(N - 1);
  for (ll i = 0; (i) < (ll)(N - 1); ++(i)) B[i] = A[i + 1] - A[i];
  struct T {
    ll a, b, c;
  };
  auto seg_f = [&](T x, T y) -> T {
    return T({max(x.a, y.a), max(x.b, y.b), max(x.c, y.c)});
  };
  SegTree<T> seg(seg_f, T({-INF, -INF, -INF}));
  auto set = [&](ll i) -> void {
    if (i == 0 || i == N - 1) return;
    ll a = B[i - 1], b = B[i];
    T t;
    if (a >= 0 && b >= 0) {
      t.a = -INF, t.b = 0, t.c = -2 * b;
    }
    if (a <= 0 && b <= 0) {
      t.a = -INF, t.b = 0, t.c = 2 * a;
    }
    if (a >= 0 && b <= 0) {
      t.a = -INF, t.b = -INF, t.c = 0;
    }
    if (a <= 0 && b >= 0) {
      ll p = min(-a, b), q = max(-a, b);
      t.a = 0, t.b = -2 * p, t.c = -2 * (p + q);
    }
    seg.set_val(i, t);
  };
  seg.init(N - 1);
  for (ll i = 0; (i) < (ll)(N - 1); ++(i)) set(i);
  ll now = 0;
  for (ll i = 0; (i) < (ll)(N - 1); ++(i)) now += abs(B[i]);
  for (ll _ = 0; (_) < (ll)(Q); ++(_)) {
    int t;
    IN(t);
    ll L, R, x;
    IN(L, R, x);
    --L;
    if (t == 1) {
      auto t = seg.fold(L, R);
      ll upd = max({-2 * x + t.a, t.b, 2 * x + t.c});
      ll ANS = now + upd;
      print(ANS);
    } else {
      if (L > 0) {
        now -= abs(B[L - 1]);
        B[L - 1] += x;
        now += abs(B[L - 1]);
        set(L - 1);
        set(L);
      }
      if (R < N) {
        now -= abs(B[R - 1]);
        B[R - 1] -= x;
        now += abs(B[R - 1]);
        set(R - 1);
        set(R);
      }
    }
  }
}
signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << setprecision(15);
  solve();
  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;
using ll = long long;
using ld = long double;
using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <class T>
T ceil(T x, T y) {
  assert(y >= 1);
  return (x > 0 ? (x + y - 1) / y : x / y);
}
template <class T>
T floor(T x, T y) {
  assert(y >= 1);
  return (x > 0 ? x / y : (x - y + 1) / y);
}
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(long double &a) { cin >> a; }
void scan(string &a) { cin >> a; }
template <class T, class S>
void scan(pair<T, S> &p) {
  scan(p.first), scan(p.second);
}
template <class T>
void scan(vector<T> &a) {
  for (auto &i : a) scan(i);
}
template <class T>
void scan(T &a) {
  cin >> a;
}
void IN() {}
template <class Head, class... Tail>
void IN(Head &head, Tail &...tail) {
  scan(head);
  IN(tail...);
}
vi s_to_vi(string S, char first_char = 'a') {
  vi A(S.size());
  for (ll i = 0; (i) < (ll)(S.size()); ++(i)) {
    A[i] = S[i] - first_char;
  }
  return A;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &A) {
  os << A.first << " " << A.second;
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &A) {
  for (size_t i = 0; i < A.size(); i++) {
    if (i) os << " ";
    os << A[i];
  }
  return os;
}
void print() { cout << "\n"; }
template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
  cout << head;
  if (sizeof...(Tail)) cout << " ";
  print(forward<Tail>(tail)...);
}
const string YESNO[2] = {"NO", "YES"};
const string YesNo[2] = {"No", "Yes"};
const string yesno[2] = {"no", "yes"};
void YES(bool t = 1) { cout << YESNO[t] << endl; }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { cout << YesNo[t] << endl; }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { cout << yesno[t] << endl; }
void no(bool t = 1) { yes(!t); }
template <typename T>
vector<T> cumsum(vector<T> A) {
  ll N = A.size();
  vector<T> B(N + 1);
  B[0] = T(0);
  for (ll i = 0; (i) < (ll)(N); ++(i)) {
    B[i + 1] = B[i] + A[i];
  }
  return B;
}
vi bin_count(vi &A, ll size) {
  vi C(size);
  for (auto &&x : A) {
    ++C[x];
  }
  return C;
}
template <typename T>
vi argsort(vector<T> &A) {
  vi ids(A.size());
  iota(ids.begin(), ids.end(), 0);
  sort(ids.begin(), ids.end(),
       [&](ll i, ll j) { return make_pair(A[i], i) <= make_pair(A[j], j); });
  return ids;
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
  return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
  return (a > b ? a = b, 1 : 0);
}
template <typename T>
struct SegTree {
  using F = function<T(T, T)>;
  int N_;
  int N;
  F seg_f;
  T T_unit;
  vector<T> dat;
  SegTree(F f, T T_unit) : seg_f(f), T_unit(T_unit) {}
  void init(int n_) {
    N_ = n_;
    N = 1;
    while (N < n_) N <<= 1;
    dat.assign(N << 1, T_unit);
  }
  void build(const vector<T> &v) {
    init(v.size());
    for (ll i = 0; (i) < (ll)(N); ++(i)) dat[N + i] = v[i];
    for (ll i = (ll)(N)-1; (i) >= (ll)(1); --(i)) {
      dat[i] = seg_f(dat[i << 1 | 0], dat[i << 1 | 1]);
    }
  }
  void set_val(int i, T x) {
    dat[i += N] = x;
    while (i >>= 1) {
      dat[i] = seg_f(dat[i << 1 | 0], dat[i << 1 | 1]);
    }
  }
  T fold(int L, int R) {
    assert(L <= R);
    T vl = T_unit, vr = T_unit;
    L += N;
    R += N;
    while (L < R) {
      if (L & 1) vl = seg_f(vl, dat[L++]);
      if (R & 1) vr = seg_f(dat[--R], vr);
      L >>= 1;
      R >>= 1;
    }
    return seg_f(vl, vr);
  }
  template <typename C>
  int max_right(int s, C &check, T &acc, int k, int l, int r) {
    if (l + 1 == r) {
      acc = seg_f(acc, dat[k]);
      return check(acc) ? -1 : k - N;
    }
    int m = (l + r) >> 1;
    if (m <= s) return max_right(s, check, acc, (k << 1) | 1, m, r);
    if (s <= l and check(seg_f(acc, dat[k]))) {
      acc = seg_f(acc, dat[k]);
      return -1;
    }
    int vl = max_right(s, check, acc, (k << 1) | 0, l, m);
    if (~vl) return vl;
    return max_right(s, check, acc, (k << 1) | 1, m, r);
  }
  template <typename C>
  int max_right(int s, C &check) {
    assert(s < N and check(T_unit));
    if (check(fold(s, N_))) return N_;
    T acc = T_unit;
    return max_right(s, check, acc, 1, 0, N);
  }
};
const ll INF = 1LL << 60;
void solve() {
  ll N;
  IN(N);
  vector<ll> A(N);
  IN(A);
  ll Q;
  IN(Q);
  vi B(N - 1);
  for (ll i = 0; (i) < (ll)(N - 1); ++(i)) B[i] = A[i + 1] - A[i];
  struct T {
    ll a, b, c;
  };
  auto seg_f = [&](T x, T y) -> T {
    return T({max(x.a, y.a), max(x.b, y.b), max(x.c, y.c)});
  };
  SegTree<T> seg(seg_f, T({-INF, -INF, -INF}));
  auto set = [&](ll i) -> void {
    if (i == 0 || i == N - 1) return;
    ll a = B[i - 1], b = B[i];
    T t;
    if (a >= 0 && b >= 0) {
      t.a = -INF, t.b = 0, t.c = -2 * b;
    }
    if (a <= 0 && b <= 0) {
      t.a = -INF, t.b = 0, t.c = 2 * a;
    }
    if (a >= 0 && b <= 0) {
      t.a = -INF, t.b = -INF, t.c = 0;
    }
    if (a <= 0 && b >= 0) {
      ll p = min(-a, b), q = max(-a, b);
      t.a = 0, t.b = -2 * p, t.c = -2 * (p + q);
    }
    seg.set_val(i, t);
  };
  seg.init(N - 1);
  for (ll i = 0; (i) < (ll)(N - 1); ++(i)) set(i);
  ll now = 0;
  for (ll i = 0; (i) < (ll)(N - 1); ++(i)) now += abs(B[i]);
  for (ll _ = 0; (_) < (ll)(Q); ++(_)) {
    int t;
    IN(t);
    ll L, R, x;
    IN(L, R, x);
    --L;
    if (t == 1) {
      auto t = seg.fold(L, R);
      ll upd = max({-2 * x + t.a, t.b, 2 * x + t.c});
      ll ANS = now + upd;
      print(ANS);
    } else {
      if (L > 0) {
        now -= abs(B[L - 1]);
        B[L - 1] += x;
        now += abs(B[L - 1]);
        set(L - 1);
        set(L);
      }
      if (R < N) {
        now -= abs(B[R - 1]);
        B[R - 1] -= x;
        now += abs(B[R - 1]);
        set(R - 1);
        set(R);
      }
    }
  }
}
signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << setprecision(15);
  solve();
  return 0;
}

```