#include <bits/stdc++.h>
using namespace std;
int arr[100005];
long long tree[400005];
long long lazy[400005];
void relax(int i, int L, int R) {
  if (lazy[i] != 0) {
    tree[i] += lazy[i] * 1LL * (R - L + 1);
    if (L != R) {
      lazy[i * 2 + 1] += lazy[i];
      lazy[i * 2 + 2] += lazy[i];
    }
    lazy[i] = 0;
  }
}
long long merge(long long a, long long b) { return a + b; }
void update(int i, int L, int R, int x, int y, long long val) {
  relax(i, L, R);
  if (L >= x && R <= y) {
    lazy[i] += val;
    relax(i, L, R);
    return;
  }
  if (L > y || R < x) return;
  update(i * 2 + 1, L, (L + R) / 2, x, y, val);
  update(i * 2 + 2, (L + R) / 2 + 1, R, x, y, val);
  tree[i] = merge(tree[i * 2 + 1], tree[i * 2 + 2]);
}
long long query(int i, int L, int R, int x, int y) {
  relax(i, L, R);
  if (L >= x && R <= y) return tree[i];
  if (L > y || R < x) return 0;
  return merge(query(i * 2 + 1, L, (L + R) / 2, x, y),
               query(i * 2 + 2, (L + R) / 2 + 1, R, x, y));
}
long long tree2[400005];
long long merge2(long long a, long long b) { return max(a, b); }
void update2(int i, int L, int R, int node, long long val) {
  if (L == R) {
    tree2[i] = val;
    return;
  }
  if (node <= (L + R) / 2)
    update2(i * 2 + 1, L, (L + R) / 2, node, val);
  else
    update2(i * 2 + 2, (L + R) / 2 + 1, R, node, val);
  tree2[i] = merge2(tree2[i * 2 + 1], tree2[i * 2 + 2]);
}
long long query2(int i, int L, int R, int x, int y) {
  if (L >= x && R <= y) return tree2[i];
  if (L > y || R < x) return -4000000000000000000LL;
  return merge2(query2(i * 2 + 1, L, (L + R) / 2, x, y),
                query2(i * 2 + 2, (L + R) / 2 + 1, R, x, y));
}
set<int> both;
set<int> les;
int n;
void fix(int i) {
  if (i == 0 || i == n - 1) return;
  long long b = query(0, 0, n - 1, i - 1, i - 1);
  long long a = query(0, 0, n - 1, i, i);
  long long c = query(0, 0, n - 1, i + 1, i + 1);
  auto it = both.find(i);
  if (it != both.end()) both.erase(it);
  it = les.find(i);
  if (it != les.end()) les.erase(it);
  if (a >= b && a >= c) {
    both.insert(i);
    update2(0, 0, n - 1, i, 4000000000000000000LL);
  } else if ((a >= b && a <= c) || (a <= b && a >= c)) {
    update2(0, 0, n - 1, i, min(a - c, a - b));
  } else {
    les.insert(i);
    update2(0, 0, n - 1, i, -4000000000000000000LL);
  }
}
long long get(int i) {
  return llabs(query(0, 0, n - 1, i, i) - query(0, 0, n - 1, i - 1, i - 1));
}
int main() {
  int c, l, r, x;
  cin >> n;
  long long first = 0;
  for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
    update(0, 0, n - 1, i, i, arr[i]);
    if (i) first += abs(arr[i] - arr[i - 1]);
  }
  for (int i = 1; i < n - 1; i++) {
    fix(i);
  }
  int q;
  cin >> q;
  while (q--) {
    scanf("%d %d %d %d", &c, &l, &r, &x);
    l--, r--;
    if (c == 1) {
      auto it = both.lower_bound(l);
      if (it != both.end() && (*it) <= r) {
        printf("%lld\n", first + 2 * x);
        continue;
      }
      long long tmp = query2(0, 0, n - 1, l, r);
      long long ans = -4000000000000000000LL;
      if (tmp != -4000000000000000000LL) {
        ans = first + x;
        ans -= -tmp;
        tmp += x;
        ans += llabs(tmp);
      }
      it = les.lower_bound(l);
      if (it != les.end() && (*it) <= r) {
        long long tmp = first;
        long long b = query(0, 0, n - 1, *it - 1, *it - 1);
        long long a = query(0, 0, n - 1, *it, *it);
        long long c = query(0, 0, n - 1, *it + 1, *it + 1);
        tmp += llabs(a + x - b) - llabs(a - b);
        tmp += llabs(a + x - c) - llabs(a - c);
        ans = max(ans, tmp);
      }
      printf("%lld\n", ans);
    } else {
      first -= get(l);
      first -= get(r + 1);
      update(0, 0, n - 1, l, r, x);
      fix(l);
      fix(l - 1);
      fix(r);
      fix(r + 1);
      first += get(l);
      first += get(r + 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 arr[100005];
long long tree[400005];
long long lazy[400005];
void relax(int i, int L, int R) {
  if (lazy[i] != 0) {
    tree[i] += lazy[i] * 1LL * (R - L + 1);
    if (L != R) {
      lazy[i * 2 + 1] += lazy[i];
      lazy[i * 2 + 2] += lazy[i];
    }
    lazy[i] = 0;
  }
}
long long merge(long long a, long long b) { return a + b; }
void update(int i, int L, int R, int x, int y, long long val) {
  relax(i, L, R);
  if (L >= x && R <= y) {
    lazy[i] += val;
    relax(i, L, R);
    return;
  }
  if (L > y || R < x) return;
  update(i * 2 + 1, L, (L + R) / 2, x, y, val);
  update(i * 2 + 2, (L + R) / 2 + 1, R, x, y, val);
  tree[i] = merge(tree[i * 2 + 1], tree[i * 2 + 2]);
}
long long query(int i, int L, int R, int x, int y) {
  relax(i, L, R);
  if (L >= x && R <= y) return tree[i];
  if (L > y || R < x) return 0;
  return merge(query(i * 2 + 1, L, (L + R) / 2, x, y),
               query(i * 2 + 2, (L + R) / 2 + 1, R, x, y));
}
long long tree2[400005];
long long merge2(long long a, long long b) { return max(a, b); }
void update2(int i, int L, int R, int node, long long val) {
  if (L == R) {
    tree2[i] = val;
    return;
  }
  if (node <= (L + R) / 2)
    update2(i * 2 + 1, L, (L + R) / 2, node, val);
  else
    update2(i * 2 + 2, (L + R) / 2 + 1, R, node, val);
  tree2[i] = merge2(tree2[i * 2 + 1], tree2[i * 2 + 2]);
}
long long query2(int i, int L, int R, int x, int y) {
  if (L >= x && R <= y) return tree2[i];
  if (L > y || R < x) return -4000000000000000000LL;
  return merge2(query2(i * 2 + 1, L, (L + R) / 2, x, y),
                query2(i * 2 + 2, (L + R) / 2 + 1, R, x, y));
}
set<int> both;
set<int> les;
int n;
void fix(int i) {
  if (i == 0 || i == n - 1) return;
  long long b = query(0, 0, n - 1, i - 1, i - 1);
  long long a = query(0, 0, n - 1, i, i);
  long long c = query(0, 0, n - 1, i + 1, i + 1);
  auto it = both.find(i);
  if (it != both.end()) both.erase(it);
  it = les.find(i);
  if (it != les.end()) les.erase(it);
  if (a >= b && a >= c) {
    both.insert(i);
    update2(0, 0, n - 1, i, 4000000000000000000LL);
  } else if ((a >= b && a <= c) || (a <= b && a >= c)) {
    update2(0, 0, n - 1, i, min(a - c, a - b));
  } else {
    les.insert(i);
    update2(0, 0, n - 1, i, -4000000000000000000LL);
  }
}
long long get(int i) {
  return llabs(query(0, 0, n - 1, i, i) - query(0, 0, n - 1, i - 1, i - 1));
}
int main() {
  int c, l, r, x;
  cin >> n;
  long long first = 0;
  for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
    update(0, 0, n - 1, i, i, arr[i]);
    if (i) first += abs(arr[i] - arr[i - 1]);
  }
  for (int i = 1; i < n - 1; i++) {
    fix(i);
  }
  int q;
  cin >> q;
  while (q--) {
    scanf("%d %d %d %d", &c, &l, &r, &x);
    l--, r--;
    if (c == 1) {
      auto it = both.lower_bound(l);
      if (it != both.end() && (*it) <= r) {
        printf("%lld\n", first + 2 * x);
        continue;
      }
      long long tmp = query2(0, 0, n - 1, l, r);
      long long ans = -4000000000000000000LL;
      if (tmp != -4000000000000000000LL) {
        ans = first + x;
        ans -= -tmp;
        tmp += x;
        ans += llabs(tmp);
      }
      it = les.lower_bound(l);
      if (it != les.end() && (*it) <= r) {
        long long tmp = first;
        long long b = query(0, 0, n - 1, *it - 1, *it - 1);
        long long a = query(0, 0, n - 1, *it, *it);
        long long c = query(0, 0, n - 1, *it + 1, *it + 1);
        tmp += llabs(a + x - b) - llabs(a - b);
        tmp += llabs(a + x - c) - llabs(a - c);
        ans = max(ans, tmp);
      }
      printf("%lld\n", ans);
    } else {
      first -= get(l);
      first -= get(r + 1);
      update(0, 0, n - 1, l, r, x);
      fix(l);
      fix(l - 1);
      fix(r);
      fix(r + 1);
      first += get(l);
      first += get(r + 1);
    }
  }
  return 0;
}

```