#include <bits/stdc++.h>
using namespace std;
int n, a[100005];
long long b[100005], S;
int aimm[4 * 100005], aipp[4 * 100005];
int nrq;
set<int> mp, pm;
int combineMM(int val1, int val2) {
  return ((b[val1 + 1] > b[val2 + 1]) ? val1 : val2);
}
int combinePP(int val1, int val2) {
  return ((b[val1] < b[val2]) ? val1 : val2);
}
int combine(int ai[], int val1, int val2) {
  if (!val1) return val2;
  if (!val2) return val1;
  if (ai == aimm) return combineMM(val1, val2);
  assert(ai == aipp);
  return combinePP(val1, val2);
}
void updateAi(int ai[], int node, int left, int right, int pos, int val) {
  if (left == right) {
    ai[node] = val;
    return;
  }
  int mid = (left + right) >> 1;
  if (pos <= mid)
    updateAi(ai, 2 * node, left, mid, pos, val);
  else
    updateAi(ai, 2 * node + 1, mid + 1, right, pos, val);
  ai[node] = combine(ai, ai[2 * node], ai[2 * node + 1]);
}
void queryAi(int ai[], int node, int left, int right, int lq, int rq,
             int &ans) {
  if (lq <= left && right <= rq) {
    ans = combine(ai, ans, ai[node]);
    return;
  }
  int mid = (left + right) >> 1;
  if (lq <= mid) queryAi(ai, 2 * node, left, mid, lq, rq, ans);
  if (mid + 1 <= rq) queryAi(ai, 2 * node + 1, mid + 1, right, lq, rq, ans);
}
void eraseEntry(int idx) {
  mp.erase(idx);
  pm.erase(idx);
  updateAi(aimm, 1, 1, n, idx, 0);
  updateAi(aipp, 1, 1, n, idx, 0);
}
void addEntry(int idx) {
  assert(2 <= idx && idx < n);
  if (b[idx] <= 0 && b[idx + 1] >= 0) mp.insert(idx);
  if (b[idx] > 0 && b[idx + 1] < 0) pm.insert(idx);
  if (b[idx] <= 0 && b[idx + 1] <= 0) updateAi(aimm, 1, 1, n, idx, idx);
  if (b[idx] >= 0 && b[idx + 1] >= 0) updateAi(aipp, 1, 1, n, idx, idx);
}
void updateB(int idx, int val, bool persistent = false) {
  if (persistent) {
    if (idx - 1 >= 2) eraseEntry(idx - 1);
    if (idx < n) eraseEntry(idx);
  }
  S -= abs(b[idx]);
  b[idx] += val;
  S += abs(b[idx]);
  if (persistent) {
    if (idx - 1 >= 2) addEntry(idx - 1);
    if (idx < n) addEntry(idx);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    b[i] = a[i - 1] - a[i];
  }
  for (int i = 2; i < n; ++i) {
    addEntry(i);
    S += abs(b[i]);
  }
  S += abs(b[n]);
  cin >> nrq;
  while (nrq--) {
    int qtype, lq, rq, x;
    cin >> qtype >> lq >> rq >> x;
    if (qtype == 1) {
      auto it = mp.lower_bound(lq);
      if (it != mp.end() && *it <= rq) {
        cout << S + 2LL * x << "\n";
        continue;
      }
      long long ans = 0;
      it = pm.lower_bound(lq);
      if (it != pm.end() && *it <= rq) {
        updateB(*it, -x);
        updateB(*it + 1, x);
        ans = max(ans, S);
        updateB(*it, x);
        updateB(*it + 1, -x);
      }
      int idx = 0;
      queryAi(aimm, 1, 1, n, lq, rq, idx);
      if (idx > 0) {
        updateB(idx, -x);
        updateB(idx + 1, x);
        ans = max(ans, S);
        updateB(idx, x);
        updateB(idx + 1, -x);
      }
      idx = 0;
      queryAi(aipp, 1, 1, n, lq, rq, idx);
      if (idx > 0) {
        updateB(idx, -x);
        updateB(idx + 1, x);
        ans = max(ans, S);
        updateB(idx, x);
        updateB(idx + 1, -x);
      }
      cout << ans << "\n";
    } else {
      updateB(lq, -x, 1);
      updateB(rq + 1, x, 1);
    }
  }
  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;
int n, a[100005];
long long b[100005], S;
int aimm[4 * 100005], aipp[4 * 100005];
int nrq;
set<int> mp, pm;
int combineMM(int val1, int val2) {
  return ((b[val1 + 1] > b[val2 + 1]) ? val1 : val2);
}
int combinePP(int val1, int val2) {
  return ((b[val1] < b[val2]) ? val1 : val2);
}
int combine(int ai[], int val1, int val2) {
  if (!val1) return val2;
  if (!val2) return val1;
  if (ai == aimm) return combineMM(val1, val2);
  assert(ai == aipp);
  return combinePP(val1, val2);
}
void updateAi(int ai[], int node, int left, int right, int pos, int val) {
  if (left == right) {
    ai[node] = val;
    return;
  }
  int mid = (left + right) >> 1;
  if (pos <= mid)
    updateAi(ai, 2 * node, left, mid, pos, val);
  else
    updateAi(ai, 2 * node + 1, mid + 1, right, pos, val);
  ai[node] = combine(ai, ai[2 * node], ai[2 * node + 1]);
}
void queryAi(int ai[], int node, int left, int right, int lq, int rq,
             int &ans) {
  if (lq <= left && right <= rq) {
    ans = combine(ai, ans, ai[node]);
    return;
  }
  int mid = (left + right) >> 1;
  if (lq <= mid) queryAi(ai, 2 * node, left, mid, lq, rq, ans);
  if (mid + 1 <= rq) queryAi(ai, 2 * node + 1, mid + 1, right, lq, rq, ans);
}
void eraseEntry(int idx) {
  mp.erase(idx);
  pm.erase(idx);
  updateAi(aimm, 1, 1, n, idx, 0);
  updateAi(aipp, 1, 1, n, idx, 0);
}
void addEntry(int idx) {
  assert(2 <= idx && idx < n);
  if (b[idx] <= 0 && b[idx + 1] >= 0) mp.insert(idx);
  if (b[idx] > 0 && b[idx + 1] < 0) pm.insert(idx);
  if (b[idx] <= 0 && b[idx + 1] <= 0) updateAi(aimm, 1, 1, n, idx, idx);
  if (b[idx] >= 0 && b[idx + 1] >= 0) updateAi(aipp, 1, 1, n, idx, idx);
}
void updateB(int idx, int val, bool persistent = false) {
  if (persistent) {
    if (idx - 1 >= 2) eraseEntry(idx - 1);
    if (idx < n) eraseEntry(idx);
  }
  S -= abs(b[idx]);
  b[idx] += val;
  S += abs(b[idx]);
  if (persistent) {
    if (idx - 1 >= 2) addEntry(idx - 1);
    if (idx < n) addEntry(idx);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    b[i] = a[i - 1] - a[i];
  }
  for (int i = 2; i < n; ++i) {
    addEntry(i);
    S += abs(b[i]);
  }
  S += abs(b[n]);
  cin >> nrq;
  while (nrq--) {
    int qtype, lq, rq, x;
    cin >> qtype >> lq >> rq >> x;
    if (qtype == 1) {
      auto it = mp.lower_bound(lq);
      if (it != mp.end() && *it <= rq) {
        cout << S + 2LL * x << "\n";
        continue;
      }
      long long ans = 0;
      it = pm.lower_bound(lq);
      if (it != pm.end() && *it <= rq) {
        updateB(*it, -x);
        updateB(*it + 1, x);
        ans = max(ans, S);
        updateB(*it, x);
        updateB(*it + 1, -x);
      }
      int idx = 0;
      queryAi(aimm, 1, 1, n, lq, rq, idx);
      if (idx > 0) {
        updateB(idx, -x);
        updateB(idx + 1, x);
        ans = max(ans, S);
        updateB(idx, x);
        updateB(idx + 1, -x);
      }
      idx = 0;
      queryAi(aipp, 1, 1, n, lq, rq, idx);
      if (idx > 0) {
        updateB(idx, -x);
        updateB(idx + 1, x);
        ans = max(ans, S);
        updateB(idx, x);
        updateB(idx + 1, -x);
      }
      cout << ans << "\n";
    } else {
      updateB(lq, -x, 1);
      updateB(rq + 1, x, 1);
    }
  }
  return 0;
}

```