#include <bits/stdc++.h>
using namespace std;
inline int getidx(const vector<int>& ar, int x) {
  lower_bound(ar.begin(), ar.end(), x) - ar.begin();
}
inline long long GCD(long long a, long long b) {
  long long n;
  if (a < b) swap(a, b);
  while (b != 0) {
    n = a % b;
    a = b;
    b = n;
  }
  return a;
}
inline long long LCM(long long a, long long b) {
  if (a == 0 || b == 0) return GCD(a, b);
  return a / GCD(a, b) * b;
}
inline long long CEIL(long long n, long long d) {
  return n / d + (long long)(n % d != 0);
}
inline long long ROUND(long long n, long long d) {
  return n / d + (long long)((n % d) * 2 >= d);
}
inline long long POW(long long a, long long n) {
  if (n < 0) return 0;
  long long ret = 1;
  while (n) {
    if (n % 2) ret *= a;
    a = a * a;
    n /= 2;
  }
  return ret;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
const long long INF = 0x3fffffffffffffff;
struct segtree {
  int n;
  vector<long long> t;
  segtree(int n) : n(n), t(2 * n) {}
  void update(int u, long long x) {
    int tar = u + n;
    for (t[u += n] = x; u > 1; u /= 2) {
      t[u / 2] = min(t[u], t[u ^ 1]);
    }
  }
  long long query(int s, int e) {
    long long ret = INF;
    for (s += n, e += n; s < e; s /= 2, e /= 2) {
      if (s & 1) ret = min(ret, t[s++]);
      if (e & 1) ret = min(ret, t[--e]);
    }
    return ret;
  }
};
const int MAXN = 1e5 + 10;
int n, q;
long long d[MAXN], sum;
segtree st(MAXN);
void input() {
  cin >> n;
  for (int(i) = (0); (i) < (int)(n); ++(i)) cin >> d[i];
  cin >> q;
}
void update(int i) { st.update(i, max(0ll, -d[i]) + max(0ll, d[i + 1])); }
int solve() {
  sum = 0;
  for (int(i) = (n - 1); (i) >= (int)(1); --(i))
    d[i] = d[i] - d[i - 1], sum += abs(d[i]);
  for (int(i) = (0); (i) < (int)(n - 1); ++(i)) update(i);
  while (q--) {
    int t;
    long long s, e, x;
    cin >> t >> s >> e >> x;
    --s, --e;
    if (t == 1) {
      if (s == e)
        cout << sum + abs(d[s] + x) - abs(d[s]) + abs(d[s + 1] - x) -
                    abs(d[s + 1])
             << '\n';
      else
        cout << sum + max(0ll, 2 * (x - st.query(s, e + 1))) << '\n';
    } else {
      for (int i : {s, e + 1})
        sum -= abs(d[i]), sum += abs(d[i] += (i == s ? x : -x));
      for (int i : {s - 1, s, e, e + 1}) update(i);
    }
  }
  return 0;
}
void execute() { input(), solve(); }
int main(void) {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  execute();
  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;
inline int getidx(const vector<int>& ar, int x) {
  lower_bound(ar.begin(), ar.end(), x) - ar.begin();
}
inline long long GCD(long long a, long long b) {
  long long n;
  if (a < b) swap(a, b);
  while (b != 0) {
    n = a % b;
    a = b;
    b = n;
  }
  return a;
}
inline long long LCM(long long a, long long b) {
  if (a == 0 || b == 0) return GCD(a, b);
  return a / GCD(a, b) * b;
}
inline long long CEIL(long long n, long long d) {
  return n / d + (long long)(n % d != 0);
}
inline long long ROUND(long long n, long long d) {
  return n / d + (long long)((n % d) * 2 >= d);
}
inline long long POW(long long a, long long n) {
  if (n < 0) return 0;
  long long ret = 1;
  while (n) {
    if (n % 2) ret *= a;
    a = a * a;
    n /= 2;
  }
  return ret;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
const long long INF = 0x3fffffffffffffff;
struct segtree {
  int n;
  vector<long long> t;
  segtree(int n) : n(n), t(2 * n) {}
  void update(int u, long long x) {
    int tar = u + n;
    for (t[u += n] = x; u > 1; u /= 2) {
      t[u / 2] = min(t[u], t[u ^ 1]);
    }
  }
  long long query(int s, int e) {
    long long ret = INF;
    for (s += n, e += n; s < e; s /= 2, e /= 2) {
      if (s & 1) ret = min(ret, t[s++]);
      if (e & 1) ret = min(ret, t[--e]);
    }
    return ret;
  }
};
const int MAXN = 1e5 + 10;
int n, q;
long long d[MAXN], sum;
segtree st(MAXN);
void input() {
  cin >> n;
  for (int(i) = (0); (i) < (int)(n); ++(i)) cin >> d[i];
  cin >> q;
}
void update(int i) { st.update(i, max(0ll, -d[i]) + max(0ll, d[i + 1])); }
int solve() {
  sum = 0;
  for (int(i) = (n - 1); (i) >= (int)(1); --(i))
    d[i] = d[i] - d[i - 1], sum += abs(d[i]);
  for (int(i) = (0); (i) < (int)(n - 1); ++(i)) update(i);
  while (q--) {
    int t;
    long long s, e, x;
    cin >> t >> s >> e >> x;
    --s, --e;
    if (t == 1) {
      if (s == e)
        cout << sum + abs(d[s] + x) - abs(d[s]) + abs(d[s + 1] - x) -
                    abs(d[s + 1])
             << '\n';
      else
        cout << sum + max(0ll, 2 * (x - st.query(s, e + 1))) << '\n';
    } else {
      for (int i : {s, e + 1})
        sum -= abs(d[i]), sum += abs(d[i] += (i == s ? x : -x));
      for (int i : {s - 1, s, e, e + 1}) update(i);
    }
  }
  return 0;
}
void execute() { input(), solve(); }
int main(void) {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  execute();
  return 0;
}

```