#include <bits/stdc++.h>
using namespace std;
long long n, arr[100009];
long long tree1[100009];
long long query1(int idx) {
  long long sum = 0;
  while (idx > 0) {
    sum += tree1[idx];
    idx -= idx & (-idx);
  }
  return sum;
}
void update1(int idx, long long x) {
  while (idx <= n) {
    tree1[idx] += x;
    idx += idx & (-idx);
  }
}
pair<long long, long long> tree[300009];
void build(int node, int b, int e) {
  if (b == e) {
    tree[node] = make_pair(
        max(0LL, arr[b - 1] - arr[b]) + max(0LL, arr[b + 1] - arr[b]), b);
    return;
  }
  int mid = (b + e) / 2;
  build(2 * node, b, mid);
  build(2 * node + 1, mid + 1, e);
  tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}
pair<long long, long long> query(int node, int b, int e, int i, int j) {
  if (e < i || b > j) return make_pair(1e18, 1e18);
  if (b >= i && e <= j) return tree[node];
  int mid = (b + e) / 2;
  return min(query(2 * node, b, mid, i, j),
             query(2 * node + 1, mid + 1, e, i, j));
}
void update(int node, int b, int e, int i, long long val) {
  if (e < i || b > i) return;
  if (b == e) {
    tree[node] = make_pair(val, b);
    return;
  }
  int mid = (b + e) / 2;
  update(2 * node, b, mid, i, val);
  update(2 * node + 1, mid + 1, e, i, val);
  tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}
long long tree2[300009];
void build2(int node, int b, int e) {
  if (b == e) {
    tree2[node] =
        min(max(0LL, arr[b - 1] - arr[b]), max(0LL, arr[b + 1] - arr[b]));
    return;
  }
  int mid = (b + e) / 2;
  build2(2 * node, b, mid);
  build2(2 * node + 1, mid + 1, e);
  tree2[node] = min(tree2[2 * node], tree2[2 * node + 1]);
}
long long query2(int node, int b, int e, int i, int j) {
  if (e < i || b > j) return 1e18;
  if (b >= i && e <= j) return tree2[node];
  int mid = (b + e) / 2;
  return min(query2(2 * node, b, mid, i, j),
             query2(2 * node + 1, mid + 1, e, i, j));
}
void update2(int node, int b, int e, int i, long long val) {
  if (e < i || b > i) return;
  if (b == e) {
    tree2[node] = val;
    return;
  }
  int mid = (b + e) / 2;
  update2(2 * node, b, mid, i, val);
  update2(2 * node + 1, mid + 1, e, i, val);
  tree2[node] = min(tree2[2 * node], tree2[2 * node + 1]);
}
vector<int> v;
int main() {
  scanf("%lld", &n);
  for (int i = 1; i <= n; i++) scanf("%lld", &arr[i]);
  int q;
  scanf("%d", &q);
  long long t, l, r, x;
  long long add = 0;
  for (int i = 1; i < n; i++) add += fabs(arr[i + 1] - arr[i]);
  build(1, 1, n);
  build2(1, 1, n);
  while (q--) {
    scanf("%lld %lld %lld %lld", &t, &l, &r, &x);
    if (t == 1) {
      long long val = -1e18;
      long long L = max(l, 2LL), R = min(r, n - 1);
      if (L <= R) {
        val = query(1, 1, n, L, R).first;
        val *= 2;
        val = 2 * x - val;
        val = max(val, -2LL * min(query2(1, 1, n, L, R), x));
      }
      if (l == 1) {
        long long v1 = arr[2] + query1(2) - arr[1] - query1(1);
        v1 = fabs(v1);
        long long v2 = arr[2] + query1(2) - arr[1] - query1(1) - x;
        v2 = fabs(v2);
        val = max(val, v2 - v1);
      }
      if (r == n) {
        long long v1 = arr[n] + query1(n) - arr[n - 1] - query1(n - 1);
        v1 = fabs(v1);
        long long v2 = arr[n] + query1(n) - arr[n - 1] - query1(n - 1) + x;
        v2 = fabs(v2);
        val = max(val, v2 - v1);
      }
      val += add;
      printf("%lld\n", val);
    } else {
      v.clear();
      if (l - 1 > 0) v.push_back(l - 1);
      if (l > 0) v.push_back(l);
      if (l != r) v.push_back(r);
      if (r + 1 <= n) v.push_back(r + 1);
      for (int i = 0; i < v.size(); i++) {
        int ind = v[i];
        if (ind - 1 > 0 && !(i > 0 && v[i - 1] == ind - 1)) {
          long long v1 = arr[ind - 1] - arr[ind];
          v1 += query1(ind - 1);
          v1 -= query1(ind);
          add -= fabs(v1);
        }
        if (ind + 1 <= n) {
          long long v1 = arr[ind + 1] - arr[ind];
          v1 += query1(ind + 1);
          v1 -= query1(ind);
          add -= fabs(v1);
        }
      }
      update1(l, x);
      if (r != n) update1(r + 1, -x);
      for (int i = 0; i < v.size(); i++) {
        int ind = v[i];
        long long v1, v2;
        v1 = arr[ind - 1] - arr[ind];
        if (ind - 1 > 0) v1 += query1(ind - 1);
        v1 -= query1(ind);
        v2 = arr[ind + 1] - arr[ind];
        if (ind + 1 <= n) v2 += query1(ind + 1);
        v2 -= query1(ind);
        update(1, 1, n, ind, max(0LL, v1) + max(0LL, v2));
        update2(1, 1, n, ind, min(max(0LL, v1), max(0LL, v2)));
      }
      for (int i = 0; i < v.size(); i++) {
        int ind = v[i];
        if (ind - 1 > 0 && !(i > 0 && v[i - 1] == ind - 1)) {
          long long v1 = arr[ind - 1] - arr[ind];
          v1 += query1(ind - 1);
          v1 -= query1(ind);
          add += fabs(v1);
        }
        if (ind + 1 <= n) {
          long long v1 = arr[ind + 1] - arr[ind];
          v1 += query1(ind + 1);
          v1 -= query1(ind);
          add += fabs(v1);
        }
      }
    }
  }
  return 0;
}

### Prompt

Please create a solution in cpp to 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;
long long n, arr[100009];
long long tree1[100009];
long long query1(int idx) {
  long long sum = 0;
  while (idx > 0) {
    sum += tree1[idx];
    idx -= idx & (-idx);
  }
  return sum;
}
void update1(int idx, long long x) {
  while (idx <= n) {
    tree1[idx] += x;
    idx += idx & (-idx);
  }
}
pair<long long, long long> tree[300009];
void build(int node, int b, int e) {
  if (b == e) {
    tree[node] = make_pair(
        max(0LL, arr[b - 1] - arr[b]) + max(0LL, arr[b + 1] - arr[b]), b);
    return;
  }
  int mid = (b + e) / 2;
  build(2 * node, b, mid);
  build(2 * node + 1, mid + 1, e);
  tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}
pair<long long, long long> query(int node, int b, int e, int i, int j) {
  if (e < i || b > j) return make_pair(1e18, 1e18);
  if (b >= i && e <= j) return tree[node];
  int mid = (b + e) / 2;
  return min(query(2 * node, b, mid, i, j),
             query(2 * node + 1, mid + 1, e, i, j));
}
void update(int node, int b, int e, int i, long long val) {
  if (e < i || b > i) return;
  if (b == e) {
    tree[node] = make_pair(val, b);
    return;
  }
  int mid = (b + e) / 2;
  update(2 * node, b, mid, i, val);
  update(2 * node + 1, mid + 1, e, i, val);
  tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}
long long tree2[300009];
void build2(int node, int b, int e) {
  if (b == e) {
    tree2[node] =
        min(max(0LL, arr[b - 1] - arr[b]), max(0LL, arr[b + 1] - arr[b]));
    return;
  }
  int mid = (b + e) / 2;
  build2(2 * node, b, mid);
  build2(2 * node + 1, mid + 1, e);
  tree2[node] = min(tree2[2 * node], tree2[2 * node + 1]);
}
long long query2(int node, int b, int e, int i, int j) {
  if (e < i || b > j) return 1e18;
  if (b >= i && e <= j) return tree2[node];
  int mid = (b + e) / 2;
  return min(query2(2 * node, b, mid, i, j),
             query2(2 * node + 1, mid + 1, e, i, j));
}
void update2(int node, int b, int e, int i, long long val) {
  if (e < i || b > i) return;
  if (b == e) {
    tree2[node] = val;
    return;
  }
  int mid = (b + e) / 2;
  update2(2 * node, b, mid, i, val);
  update2(2 * node + 1, mid + 1, e, i, val);
  tree2[node] = min(tree2[2 * node], tree2[2 * node + 1]);
}
vector<int> v;
int main() {
  scanf("%lld", &n);
  for (int i = 1; i <= n; i++) scanf("%lld", &arr[i]);
  int q;
  scanf("%d", &q);
  long long t, l, r, x;
  long long add = 0;
  for (int i = 1; i < n; i++) add += fabs(arr[i + 1] - arr[i]);
  build(1, 1, n);
  build2(1, 1, n);
  while (q--) {
    scanf("%lld %lld %lld %lld", &t, &l, &r, &x);
    if (t == 1) {
      long long val = -1e18;
      long long L = max(l, 2LL), R = min(r, n - 1);
      if (L <= R) {
        val = query(1, 1, n, L, R).first;
        val *= 2;
        val = 2 * x - val;
        val = max(val, -2LL * min(query2(1, 1, n, L, R), x));
      }
      if (l == 1) {
        long long v1 = arr[2] + query1(2) - arr[1] - query1(1);
        v1 = fabs(v1);
        long long v2 = arr[2] + query1(2) - arr[1] - query1(1) - x;
        v2 = fabs(v2);
        val = max(val, v2 - v1);
      }
      if (r == n) {
        long long v1 = arr[n] + query1(n) - arr[n - 1] - query1(n - 1);
        v1 = fabs(v1);
        long long v2 = arr[n] + query1(n) - arr[n - 1] - query1(n - 1) + x;
        v2 = fabs(v2);
        val = max(val, v2 - v1);
      }
      val += add;
      printf("%lld\n", val);
    } else {
      v.clear();
      if (l - 1 > 0) v.push_back(l - 1);
      if (l > 0) v.push_back(l);
      if (l != r) v.push_back(r);
      if (r + 1 <= n) v.push_back(r + 1);
      for (int i = 0; i < v.size(); i++) {
        int ind = v[i];
        if (ind - 1 > 0 && !(i > 0 && v[i - 1] == ind - 1)) {
          long long v1 = arr[ind - 1] - arr[ind];
          v1 += query1(ind - 1);
          v1 -= query1(ind);
          add -= fabs(v1);
        }
        if (ind + 1 <= n) {
          long long v1 = arr[ind + 1] - arr[ind];
          v1 += query1(ind + 1);
          v1 -= query1(ind);
          add -= fabs(v1);
        }
      }
      update1(l, x);
      if (r != n) update1(r + 1, -x);
      for (int i = 0; i < v.size(); i++) {
        int ind = v[i];
        long long v1, v2;
        v1 = arr[ind - 1] - arr[ind];
        if (ind - 1 > 0) v1 += query1(ind - 1);
        v1 -= query1(ind);
        v2 = arr[ind + 1] - arr[ind];
        if (ind + 1 <= n) v2 += query1(ind + 1);
        v2 -= query1(ind);
        update(1, 1, n, ind, max(0LL, v1) + max(0LL, v2));
        update2(1, 1, n, ind, min(max(0LL, v1), max(0LL, v2)));
      }
      for (int i = 0; i < v.size(); i++) {
        int ind = v[i];
        if (ind - 1 > 0 && !(i > 0 && v[i - 1] == ind - 1)) {
          long long v1 = arr[ind - 1] - arr[ind];
          v1 += query1(ind - 1);
          v1 -= query1(ind);
          add += fabs(v1);
        }
        if (ind + 1 <= n) {
          long long v1 = arr[ind + 1] - arr[ind];
          v1 += query1(ind + 1);
          v1 -= query1(ind);
          add += fabs(v1);
        }
      }
    }
  }
  return 0;
}

```