#include <bits/stdc++.h>
using namespace std;
long long int absolut(long long int x) {
  if (x < 0) return -x;
  return x;
}
const int tope = 1 << 18;
const int primero = 1 << 17;
long long int anyade[tope];
void anyadir(int pos0, int pos1, long long int val) {
  pos0 += primero;
  pos1 += primero;
  if (pos0 == pos1) {
    anyade[pos0] += val;
    return;
  }
  anyade[pos0] += val;
  anyade[pos1] += val;
  while (pos0 + 1 < pos1) {
    if (pos0 % 2 == 0) anyade[pos0 + 1] += val;
    pos0 /= 2;
    if (pos1 % 2 == 1) anyade[pos1 - 1] += val;
    pos1 /= 2;
  }
}
long long int getvalue(int pos) {
  pos += primero;
  long long int s = anyade[pos];
  while (pos > 1) {
    pos /= 2;
    s += anyade[pos];
  }
  return s;
}
void getbest(long long int a1, long long int a2, long long int b1,
             long long int b2, long long int &d1, long long int &d2) {
  d1 = min(a1, b1);
  if (a1 <= b1) {
    long long int x = 2 * (b1 - a1) + b2;
    d2 = min(x, a2);
  } else {
    long long int x = 2 * (a1 - b1) + a2;
    d2 = min(x, b2);
  }
}
long long int d1[tope];
long long int d2[tope];
void inserta(int pos, long long int dd1, long long int dd2) {
  pos += primero;
  d1[pos] = dd1;
  d2[pos] = dd2;
  while (pos > 1) {
    pos /= 2;
    getbest(d1[2 * pos], d2[2 * pos], d1[2 * pos + 1], d2[2 * pos + 1], d1[pos],
            d2[pos]);
  }
}
void mejorentre(int pos0, int pos1, long long int &dd1, long long int &dd2) {
  pos0 += primero;
  pos1 += primero;
  if (pos0 == pos1) {
    dd1 = d1[pos0];
    dd2 = d2[pos0];
    return;
  }
  getbest(d1[pos0], d2[pos0], d1[pos1], d2[pos1], dd1, dd2);
  while (pos0 + 1 < pos1) {
    if (pos0 % 2 == 0) getbest(d1[pos0 + 1], d2[pos0 + 1], dd1, dd2, dd1, dd2);
    pos0 /= 2;
    if (pos1 % 2 == 1) getbest(d1[pos1 - 1], d2[pos1 - 1], dd1, dd2, dd1, dd2);
    pos1 /= 2;
  }
}
void actualiza(int i) {
  long long int x0 = getvalue(i - 1);
  long long int x1 = getvalue(i);
  long long int x2 = getvalue(i + 1);
  long long int d0 = max(0LL, min(x0 - x1, x2 - x1));
  long long int d1 = max(0LL, max(x0 - x1, x2 - x1));
  d1 -= d0;
  inserta(i, d0, d1);
}
int n;
long long int A = 0;
void escribe() {
  cout << "A: " << A << endl;
  cout << "value: ";
  for (int i = 1; i <= n; i++) cout << getvalue(i) << ",";
  cout << endl;
  cout << "D: ";
  for (int i = 2; i < n; i++)
    cout << "(" << d1[i + primero] << "," << d2[i + primero] << ")";
  cout << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    long long int a;
    cin >> a;
    anyadir(i, i, a);
  }
  for (int i = 1; i < n; i++) A += absolut(getvalue(i) - getvalue(i + 1));
  for (int i = 2; i < n; i++) actualiza(i);
  int casos;
  cin >> casos;
  for (int cas = 0; cas < casos; cas++) {
    int tipo;
    long long int l, r, x;
    cin >> tipo >> l >> r >> x;
    if (tipo == 1) {
      long long int d1, d2;
      mejorentre(l, r, d1, d2);
      long long int val = 0;
      if (x <= d1)
        val = -2 * x;
      else if (x <= d1 + d2)
        val = -2 * d1;
      else
        val = -2 * d1 + 2 * (x - d1 - d2);
      cout << A + val << endl;
    } else {
      A -= absolut(getvalue(l - 1) - getvalue(l));
      A -= absolut(getvalue(l) - getvalue(l + 1));
      if (l < r) {
        A -= absolut(getvalue(r) - getvalue(r + 1));
        if (l + 1 < r) A -= absolut(getvalue(r - 1) - getvalue(r));
      }
      anyadir(l, r, x);
      actualiza(l);
      if (l - 1 > 1) actualiza(l - 1);
      actualiza(r);
      if (r + 1 < n) actualiza(r + 1);
      A += absolut(getvalue(l - 1) - getvalue(l));
      A += absolut(getvalue(l) - getvalue(l + 1));
      if (l < r) {
        A += absolut(getvalue(r) - getvalue(r + 1));
        if (l + 1 < r) A += absolut(getvalue(r - 1) - getvalue(r));
      }
    }
  }
}

### 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;
long long int absolut(long long int x) {
  if (x < 0) return -x;
  return x;
}
const int tope = 1 << 18;
const int primero = 1 << 17;
long long int anyade[tope];
void anyadir(int pos0, int pos1, long long int val) {
  pos0 += primero;
  pos1 += primero;
  if (pos0 == pos1) {
    anyade[pos0] += val;
    return;
  }
  anyade[pos0] += val;
  anyade[pos1] += val;
  while (pos0 + 1 < pos1) {
    if (pos0 % 2 == 0) anyade[pos0 + 1] += val;
    pos0 /= 2;
    if (pos1 % 2 == 1) anyade[pos1 - 1] += val;
    pos1 /= 2;
  }
}
long long int getvalue(int pos) {
  pos += primero;
  long long int s = anyade[pos];
  while (pos > 1) {
    pos /= 2;
    s += anyade[pos];
  }
  return s;
}
void getbest(long long int a1, long long int a2, long long int b1,
             long long int b2, long long int &d1, long long int &d2) {
  d1 = min(a1, b1);
  if (a1 <= b1) {
    long long int x = 2 * (b1 - a1) + b2;
    d2 = min(x, a2);
  } else {
    long long int x = 2 * (a1 - b1) + a2;
    d2 = min(x, b2);
  }
}
long long int d1[tope];
long long int d2[tope];
void inserta(int pos, long long int dd1, long long int dd2) {
  pos += primero;
  d1[pos] = dd1;
  d2[pos] = dd2;
  while (pos > 1) {
    pos /= 2;
    getbest(d1[2 * pos], d2[2 * pos], d1[2 * pos + 1], d2[2 * pos + 1], d1[pos],
            d2[pos]);
  }
}
void mejorentre(int pos0, int pos1, long long int &dd1, long long int &dd2) {
  pos0 += primero;
  pos1 += primero;
  if (pos0 == pos1) {
    dd1 = d1[pos0];
    dd2 = d2[pos0];
    return;
  }
  getbest(d1[pos0], d2[pos0], d1[pos1], d2[pos1], dd1, dd2);
  while (pos0 + 1 < pos1) {
    if (pos0 % 2 == 0) getbest(d1[pos0 + 1], d2[pos0 + 1], dd1, dd2, dd1, dd2);
    pos0 /= 2;
    if (pos1 % 2 == 1) getbest(d1[pos1 - 1], d2[pos1 - 1], dd1, dd2, dd1, dd2);
    pos1 /= 2;
  }
}
void actualiza(int i) {
  long long int x0 = getvalue(i - 1);
  long long int x1 = getvalue(i);
  long long int x2 = getvalue(i + 1);
  long long int d0 = max(0LL, min(x0 - x1, x2 - x1));
  long long int d1 = max(0LL, max(x0 - x1, x2 - x1));
  d1 -= d0;
  inserta(i, d0, d1);
}
int n;
long long int A = 0;
void escribe() {
  cout << "A: " << A << endl;
  cout << "value: ";
  for (int i = 1; i <= n; i++) cout << getvalue(i) << ",";
  cout << endl;
  cout << "D: ";
  for (int i = 2; i < n; i++)
    cout << "(" << d1[i + primero] << "," << d2[i + primero] << ")";
  cout << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    long long int a;
    cin >> a;
    anyadir(i, i, a);
  }
  for (int i = 1; i < n; i++) A += absolut(getvalue(i) - getvalue(i + 1));
  for (int i = 2; i < n; i++) actualiza(i);
  int casos;
  cin >> casos;
  for (int cas = 0; cas < casos; cas++) {
    int tipo;
    long long int l, r, x;
    cin >> tipo >> l >> r >> x;
    if (tipo == 1) {
      long long int d1, d2;
      mejorentre(l, r, d1, d2);
      long long int val = 0;
      if (x <= d1)
        val = -2 * x;
      else if (x <= d1 + d2)
        val = -2 * d1;
      else
        val = -2 * d1 + 2 * (x - d1 - d2);
      cout << A + val << endl;
    } else {
      A -= absolut(getvalue(l - 1) - getvalue(l));
      A -= absolut(getvalue(l) - getvalue(l + 1));
      if (l < r) {
        A -= absolut(getvalue(r) - getvalue(r + 1));
        if (l + 1 < r) A -= absolut(getvalue(r - 1) - getvalue(r));
      }
      anyadir(l, r, x);
      actualiza(l);
      if (l - 1 > 1) actualiza(l - 1);
      actualiza(r);
      if (r + 1 < n) actualiza(r + 1);
      A += absolut(getvalue(l - 1) - getvalue(l));
      A += absolut(getvalue(l) - getvalue(l + 1));
      if (l < r) {
        A += absolut(getvalue(r) - getvalue(r + 1));
        if (l + 1 < r) A += absolut(getvalue(r - 1) - getvalue(r));
      }
    }
  }
}

```