#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100010;
const ll inf = 1ll << 60;
struct rq {
  vector<ll> t;
  int n;
  rq(vector<int>& v) : t(2 * v.size(), 0), n(v.size()) {
    copy(v.begin(), v.end(), t.begin() + n);
  }
  void update(int l, int r, int v) {
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) t[l++] += v;
      if (r & 1) t[--r] += v;
    }
  }
  ll query(int p) {
    ll r = 0;
    for (p += n; p > 0; p >>= 1) {
      r += t[p];
    }
    return r;
  }
};
ll t[4 * N][2];
void build(int i, int l, int r) {
  if (l == r) {
    t[i][0] = t[i][1] = inf;
  } else {
    int m = l + r >> 1;
    build(2 * i, l, m);
    build(2 * i + 1, m + 1, r);
    t[i][0] = t[i][1] = inf;
  }
}
void update(int i, int l, int r, int p, ll v0, ll v1) {
  if (l == r) {
    t[i][0] = v0;
    t[i][1] = v0 + v1;
  } else {
    int m = l + r >> 1;
    if (p <= m)
      update(2 * i, l, m, p, v0, v1);
    else
      update(2 * i + 1, m + 1, r, p, v0, v1);
    t[i][0] = min(t[2 * i][0], t[2 * i + 1][0]);
    t[i][1] = min(t[2 * i][1], t[2 * i + 1][1]);
  }
}
ll query(int i, int l, int r, int ql, int qr, int k) {
  if (r < ql || qr < l) return inf;
  if (ql <= l && r <= qr) return t[i][k];
  int m = l + r >> 1;
  return min(query(2 * i, l, m, ql, qr, k),
             query(2 * i + 1, m + 1, r, ql, qr, k));
}
void print(int i, int l, int r) {
  if (l == r) {
    cout << "(" << t[i][0] << ", " << t[i][1] << ") ";
  } else {
    int m = l + r >> 1;
    print(2 * i, l, m);
    print(2 * i + 1, m + 1, r);
  }
}
int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  n--;
  vector<int> v(n + 1);
  ll ans = 0;
  for (int i = 0; i <= n; i++) {
    cin >> v[i];
    if (i) ans += abs(v[i] - v[i - 1]);
  }
  build(1, 0, n);
  for (int i = 1; i <= n - 1; i++) {
    ll v0 = max(v[i - 1] - v[i], 0);
    ll v1 = max(v[i + 1] - v[i], 0);
    if (v0 > v1) swap(v0, v1);
    update(1, 0, n, i, v0, v1);
  }
  rq seg(v);
  auto test = [&](int i, ll s = 0) {
    ll r = 0;
    if (i - 1 >= 0) r += abs(seg.query(i) + s - seg.query(i - 1));
    if (i + 1 <= n) r += abs(seg.query(i) + s - seg.query(i + 1));
    return r;
  };
  int q;
  cin >> q;
  while (q--) {
    int op, l, r, x;
    cin >> op >> l >> r >> x;
    l--, r--;
    if (op == 1) {
      ll dt = -2 * x;
      dt = max(dt, 2 * x - 2 * query(1, 0, n, l + 1, r, 1));
      dt = max(dt, -2 * query(1, 0, n, l + 1, r, 0));
      dt = max(dt, test(l, x) - test(l));
      dt = max(dt, test(r, x) - test(r));
      cout << (ans + dt) << "\n";
    } else {
      set<int> pos;
      if (l - 1 >= 0) pos.insert(l);
      if (l + 1 <= n) pos.insert(l + 1);
      if (r - 1 >= 0) pos.insert(r);
      if (r + 1 <= n) pos.insert(r + 1);
      for (int p : pos) {
        ans -= abs(seg.query(p) - seg.query(p - 1));
      }
      seg.update(l, r + 1, x);
      for (int p : pos) {
        ans += abs(seg.query(p) - seg.query(p - 1));
      }
      if (l > 0) {
        {
          ll v0 = max(seg.query(l - 1) - seg.query(l), 0ll);
          ll v1 = max(seg.query(l + 1) - seg.query(l), 0ll);
          if (v0 > v1) swap(v0, v1);
          update(1, 0, n, l, v0, v1);
        }
        if (l - 1 > 0) {
          ll v0 = max(seg.query(l - 2) - seg.query(l - 1), 0ll);
          ll v1 = max(seg.query(l) - seg.query(l - 1), 0ll);
          if (v0 > v1) swap(v0, v1);
          update(1, 0, n, l - 1, v0, v1);
        }
      }
      if (r < n) {
        {
          ll v0 = max(seg.query(r - 1) - seg.query(r), 0ll);
          ll v1 = max(seg.query(r + 1) - seg.query(r), 0ll);
          if (v0 > v1) swap(v0, v1);
          update(1, 0, n, r, v0, v1);
        }
        if (r + 1 < n) {
          ll v0 = max(seg.query(r) - seg.query(r + 1), 0ll);
          ll v1 = max(seg.query(r + 2) - seg.query(r + 1), 0ll);
          if (v0 > v1) swap(v0, v1);
          update(1, 0, n, r + 1, v0, v1);
        }
      }
    }
  }
  return 0;
}

### Prompt

In Cpp, your task is to solve 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;
const int N = 100010;
const ll inf = 1ll << 60;
struct rq {
  vector<ll> t;
  int n;
  rq(vector<int>& v) : t(2 * v.size(), 0), n(v.size()) {
    copy(v.begin(), v.end(), t.begin() + n);
  }
  void update(int l, int r, int v) {
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) t[l++] += v;
      if (r & 1) t[--r] += v;
    }
  }
  ll query(int p) {
    ll r = 0;
    for (p += n; p > 0; p >>= 1) {
      r += t[p];
    }
    return r;
  }
};
ll t[4 * N][2];
void build(int i, int l, int r) {
  if (l == r) {
    t[i][0] = t[i][1] = inf;
  } else {
    int m = l + r >> 1;
    build(2 * i, l, m);
    build(2 * i + 1, m + 1, r);
    t[i][0] = t[i][1] = inf;
  }
}
void update(int i, int l, int r, int p, ll v0, ll v1) {
  if (l == r) {
    t[i][0] = v0;
    t[i][1] = v0 + v1;
  } else {
    int m = l + r >> 1;
    if (p <= m)
      update(2 * i, l, m, p, v0, v1);
    else
      update(2 * i + 1, m + 1, r, p, v0, v1);
    t[i][0] = min(t[2 * i][0], t[2 * i + 1][0]);
    t[i][1] = min(t[2 * i][1], t[2 * i + 1][1]);
  }
}
ll query(int i, int l, int r, int ql, int qr, int k) {
  if (r < ql || qr < l) return inf;
  if (ql <= l && r <= qr) return t[i][k];
  int m = l + r >> 1;
  return min(query(2 * i, l, m, ql, qr, k),
             query(2 * i + 1, m + 1, r, ql, qr, k));
}
void print(int i, int l, int r) {
  if (l == r) {
    cout << "(" << t[i][0] << ", " << t[i][1] << ") ";
  } else {
    int m = l + r >> 1;
    print(2 * i, l, m);
    print(2 * i + 1, m + 1, r);
  }
}
int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  n--;
  vector<int> v(n + 1);
  ll ans = 0;
  for (int i = 0; i <= n; i++) {
    cin >> v[i];
    if (i) ans += abs(v[i] - v[i - 1]);
  }
  build(1, 0, n);
  for (int i = 1; i <= n - 1; i++) {
    ll v0 = max(v[i - 1] - v[i], 0);
    ll v1 = max(v[i + 1] - v[i], 0);
    if (v0 > v1) swap(v0, v1);
    update(1, 0, n, i, v0, v1);
  }
  rq seg(v);
  auto test = [&](int i, ll s = 0) {
    ll r = 0;
    if (i - 1 >= 0) r += abs(seg.query(i) + s - seg.query(i - 1));
    if (i + 1 <= n) r += abs(seg.query(i) + s - seg.query(i + 1));
    return r;
  };
  int q;
  cin >> q;
  while (q--) {
    int op, l, r, x;
    cin >> op >> l >> r >> x;
    l--, r--;
    if (op == 1) {
      ll dt = -2 * x;
      dt = max(dt, 2 * x - 2 * query(1, 0, n, l + 1, r, 1));
      dt = max(dt, -2 * query(1, 0, n, l + 1, r, 0));
      dt = max(dt, test(l, x) - test(l));
      dt = max(dt, test(r, x) - test(r));
      cout << (ans + dt) << "\n";
    } else {
      set<int> pos;
      if (l - 1 >= 0) pos.insert(l);
      if (l + 1 <= n) pos.insert(l + 1);
      if (r - 1 >= 0) pos.insert(r);
      if (r + 1 <= n) pos.insert(r + 1);
      for (int p : pos) {
        ans -= abs(seg.query(p) - seg.query(p - 1));
      }
      seg.update(l, r + 1, x);
      for (int p : pos) {
        ans += abs(seg.query(p) - seg.query(p - 1));
      }
      if (l > 0) {
        {
          ll v0 = max(seg.query(l - 1) - seg.query(l), 0ll);
          ll v1 = max(seg.query(l + 1) - seg.query(l), 0ll);
          if (v0 > v1) swap(v0, v1);
          update(1, 0, n, l, v0, v1);
        }
        if (l - 1 > 0) {
          ll v0 = max(seg.query(l - 2) - seg.query(l - 1), 0ll);
          ll v1 = max(seg.query(l) - seg.query(l - 1), 0ll);
          if (v0 > v1) swap(v0, v1);
          update(1, 0, n, l - 1, v0, v1);
        }
      }
      if (r < n) {
        {
          ll v0 = max(seg.query(r - 1) - seg.query(r), 0ll);
          ll v1 = max(seg.query(r + 1) - seg.query(r), 0ll);
          if (v0 > v1) swap(v0, v1);
          update(1, 0, n, r, v0, v1);
        }
        if (r + 1 < n) {
          ll v0 = max(seg.query(r) - seg.query(r + 1), 0ll);
          ll v1 = max(seg.query(r + 2) - seg.query(r + 1), 0ll);
          if (v0 > v1) swap(v0, v1);
          update(1, 0, n, r + 1, v0, v1);
        }
      }
    }
  }
  return 0;
}

```