#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const long long INF = 1e18;
int n, q;
long long a[N];
long long f[N][2][2];
long long sum;
long long lazy;
long long it[N * 4][2][2];
void calcF(int id) {
  f[id][0][0] = a[id] + a[id + 1];
  f[id][0][1] = a[id] - a[id + 1];
  f[id][1][0] = -a[id] + a[id + 1];
  f[id][1][1] = -a[id] - a[id + 1];
}
void modify(int id) {
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      it[id][i][j] = max(it[id << 1][i][j], it[id << 1 | 1][i][j]);
    }
  }
}
void modify(int id, int p) {
  calcF(p);
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      it[id][i][j] = f[p][i][j] + sum - abs(a[p]) - abs(a[p + 1]);
    }
  }
}
void build(int i, int l, int r) {
  if (l == r) {
    modify(i, l);
    return;
  }
  int mid = (l + r) >> 1;
  build(i << 1, l, mid);
  build(i << 1 | 1, mid + 1, r);
  modify(i);
}
void upd(int i, int l, int r, int p) {
  if (l == r) {
    modify(i, l);
    return;
  }
  int mid = (l + r) >> 1;
  if (mid >= p)
    upd(i << 1, l, mid, p);
  else
    upd(i << 1 | 1, mid + 1, r, p);
  modify(i);
}
long long res[2][2];
void get(int i, int l, int r, int L, int R) {
  if (l > R || L > r) return;
  if (L <= l && r <= R) {
    for (int j = 0; j < 2; ++j) {
      for (int k = 0; k < 2; ++k) {
        res[j][k] = max(res[j][k], it[i][j][k]);
      }
    }
    return;
  }
  int mid = (l + r) >> 1;
  get(i << 1, l, mid, L, R);
  get(i << 1 | 1, mid + 1, r, L, R);
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = n; i >= 1; --i) a[i] -= a[i - 1];
  for (int i = 2; i <= n; ++i) sum += abs(a[i]);
  build(1, 2, n - 1);
  cin >> q;
  while (q--) {
    int t, l, r, x;
    cin >> t >> l >> r >> x;
    if (t == 1) {
      for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
          res[i][j] = -INF;
        }
      }
      get(1, 2, n - 1, l, r);
      long long Res = -INF;
      Res = max(Res, res[0][0]);
      Res = max(Res, res[0][1] + 2 * x);
      Res = max(Res, res[1][0] - 2 * x);
      Res = max(Res, res[1][1]);
      if (l == 1) {
        Res = max(Res, sum + abs(a[2] - x) - abs(a[2]));
      }
      if (r == n) {
        Res = max(Res, sum + abs(a[n] + x) - abs(a[n]));
      }
      cout << Res + lazy << '\n';
    } else {
      if (l > 1) {
        lazy += abs(a[l] + x) - abs(a[l]), a[l] += x;
      }
      if (r < n) {
        lazy += abs(a[r + 1] - x) - abs(a[r + 1]), a[r + 1] -= x;
      }
      if (l > 1) upd(1, 2, n - 1, l);
      if (l - 1 > 1) upd(1, 2, n - 1, l - 1);
      if (r < n) upd(1, 2, n - 1, r);
      if (r + 1 < n) upd(1, 2, n - 1, r + 1);
    }
  }
}

### Prompt

Please provide a cpp coded solution 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;
const int N = 100005;
const long long INF = 1e18;
int n, q;
long long a[N];
long long f[N][2][2];
long long sum;
long long lazy;
long long it[N * 4][2][2];
void calcF(int id) {
  f[id][0][0] = a[id] + a[id + 1];
  f[id][0][1] = a[id] - a[id + 1];
  f[id][1][0] = -a[id] + a[id + 1];
  f[id][1][1] = -a[id] - a[id + 1];
}
void modify(int id) {
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      it[id][i][j] = max(it[id << 1][i][j], it[id << 1 | 1][i][j]);
    }
  }
}
void modify(int id, int p) {
  calcF(p);
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      it[id][i][j] = f[p][i][j] + sum - abs(a[p]) - abs(a[p + 1]);
    }
  }
}
void build(int i, int l, int r) {
  if (l == r) {
    modify(i, l);
    return;
  }
  int mid = (l + r) >> 1;
  build(i << 1, l, mid);
  build(i << 1 | 1, mid + 1, r);
  modify(i);
}
void upd(int i, int l, int r, int p) {
  if (l == r) {
    modify(i, l);
    return;
  }
  int mid = (l + r) >> 1;
  if (mid >= p)
    upd(i << 1, l, mid, p);
  else
    upd(i << 1 | 1, mid + 1, r, p);
  modify(i);
}
long long res[2][2];
void get(int i, int l, int r, int L, int R) {
  if (l > R || L > r) return;
  if (L <= l && r <= R) {
    for (int j = 0; j < 2; ++j) {
      for (int k = 0; k < 2; ++k) {
        res[j][k] = max(res[j][k], it[i][j][k]);
      }
    }
    return;
  }
  int mid = (l + r) >> 1;
  get(i << 1, l, mid, L, R);
  get(i << 1 | 1, mid + 1, r, L, R);
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = n; i >= 1; --i) a[i] -= a[i - 1];
  for (int i = 2; i <= n; ++i) sum += abs(a[i]);
  build(1, 2, n - 1);
  cin >> q;
  while (q--) {
    int t, l, r, x;
    cin >> t >> l >> r >> x;
    if (t == 1) {
      for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
          res[i][j] = -INF;
        }
      }
      get(1, 2, n - 1, l, r);
      long long Res = -INF;
      Res = max(Res, res[0][0]);
      Res = max(Res, res[0][1] + 2 * x);
      Res = max(Res, res[1][0] - 2 * x);
      Res = max(Res, res[1][1]);
      if (l == 1) {
        Res = max(Res, sum + abs(a[2] - x) - abs(a[2]));
      }
      if (r == n) {
        Res = max(Res, sum + abs(a[n] + x) - abs(a[n]));
      }
      cout << Res + lazy << '\n';
    } else {
      if (l > 1) {
        lazy += abs(a[l] + x) - abs(a[l]), a[l] += x;
      }
      if (r < n) {
        lazy += abs(a[r + 1] - x) - abs(a[r + 1]), a[r + 1] -= x;
      }
      if (l > 1) upd(1, 2, n - 1, l);
      if (l - 1 > 1) upd(1, 2, n - 1, l - 1);
      if (r < n) upd(1, 2, n - 1, r);
      if (r + 1 < n) upd(1, 2, n - 1, r + 1);
    }
  }
}

```