#include <bits/stdc++.h>
using namespace std;
long long INF = -1e18, GF, GL;
struct Vertex {
  long long l;
  long long r;
  long long pr;
  long long sz;
  long long value;
  long long p;
  bool F;
  long long S;
  long long T;
  bool f;
  long long s;
  long long t;
  long long g;
  long long G;
};
vector<Vertex> decart;
pair<long long, long long> SP = make_pair(-1, -1);
long long n, base;
void update(long long vertex) {
  if (vertex == -1) return;
  long long sz = 1, L = decart[vertex].l, R = decart[vertex].r;
  decart[vertex].F = decart[vertex].f;
  decart[vertex].S = decart[vertex].s;
  decart[vertex].T = decart[vertex].t;
  decart[vertex].G = decart[vertex].g;
  if (L != -1) {
    sz += decart[L].sz;
    decart[vertex].F |= decart[L].F;
    decart[vertex].S = max(decart[vertex].S, decart[L].S);
    decart[vertex].T = max(decart[vertex].T, decart[L].T);
    decart[vertex].G = max(decart[vertex].G, decart[L].G);
  }
  if (R != -1) {
    sz += decart[R].sz;
    decart[vertex].F |= decart[R].F;
    decart[vertex].S = max(decart[vertex].S, decart[R].S);
    decart[vertex].T = max(decart[vertex].T, decart[R].T);
    decart[vertex].G = max(decart[vertex].G, decart[R].G);
  }
  decart[vertex].sz = sz;
}
void push(long long vertex) {
  if (vertex == -1) return;
  long long pp = decart[vertex].p;
  decart[vertex].p = 0;
  if (decart[vertex].l != -1) {
    decart[decart[vertex].l].value += pp;
    decart[decart[vertex].l].p += pp;
  }
  if (decart[vertex].r != -1) {
    decart[decart[vertex].r].value += pp;
    decart[decart[vertex].r].p += pp;
  }
}
void P(long long vertex, long long wh) {
  push(vertex);
  decart[vertex].value += wh;
  decart[vertex].p += wh;
}
pair<long long, long long> split(long long father, long long number) {
  if (father == -1) return SP;
  push(father);
  long long l = 1;
  if (decart[father].l != -1) {
    l += decart[decart[father].l].sz;
  }
  if (l <= number) {
    pair<long long, long long> p = split(decart[father].r, number - l);
    decart[father].r = p.first;
    p.first = father;
    update(father);
    return p;
  }
  pair<long long, long long> p = split(decart[father].l, number);
  decart[father].l = p.second;
  p.second = father;
  update(father);
  return p;
}
long long merg(long long first, long long second) {
  push(first);
  push(second);
  if (first == -1) return second;
  if (second == -1) return first;
  if (decart[first].pr >= decart[second].pr) {
    long long v = merg(decart[first].r, second);
    decart[first].r = v;
    update(first);
    return first;
  }
  long long v = merg(first, decart[second].l);
  decart[second].l = v;
  update(second);
  return second;
}
void create(long long a, long long b, long long c) {
  Vertex v = {-1, -1, rand(), 1, b, 0};
  v.S = INF;
  v.T = INF;
  v.G = INF;
  if (b >= a && b >= c)
    v.F = true;
  else {
    v.F = false;
    if (b >= a || b >= c) {
      v.S = min(b - a, b - c);
    } else {
      v.T = 2 * (b - a + b - c);
      v.G = 2 * max(b - a, b - c);
    }
  }
  v.f = v.F;
  v.s = v.S;
  v.t = v.T;
  v.g = v.G;
  decart.push_back(v);
  base = merg(base, decart.size() - 1);
}
long long Get(long long vertex, long long sk) {
  push(vertex);
  long long L = decart[vertex].l;
  long long R = decart[vertex].r;
  if (L != -1) {
    long long sz = decart[L].sz;
    if (sz > sk) return Get(L, sk);
    sk -= sz;
  }
  if (sk == 0) return decart[vertex].value;
  return Get(R, sk - 1);
}
long long get(long long ind) {
  if (ind == 0) return GF;
  if (ind == n - 1) return GL;
  return Get(base, ind - 1);
}
void Ch(long long dind) {
  long long a = get(dind);
  long long b = get(dind + 1);
  long long c = get(dind + 2);
  pair<long long, long long> p1 = split(base, dind);
  pair<long long, long long> p2 = split(p1.second, 1);
  base = p1.first;
  create(a, b, c);
  base = merg(base, p2.second);
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  base = -1;
  cin >> n;
  vector<long long> v;
  for (long long i = 0; i < n; i++) {
    long long value;
    cin >> value;
    v.push_back(value);
  }
  GF = v[0];
  GL = v[n - 1];
  long long G = 0;
  for (long long i = 0; i < n - 1; i++) G += abs(v[i + 1] - v[i]);
  for (long long i = 1; i < n - 1; i++) {
    create(v[i - 1], v[i], v[i + 1]);
  }
  long long q;
  cin >> q;
  for (long long i = 0; i < q; i++) {
    long long t;
    cin >> t;
    if (t == 1) {
      long long L, R, X;
      cin >> L >> R >> X;
      long long ans = -2 * X;
      if (L == 1) {
        ans = max(ans, abs(X + GF - get(1)) - abs(GF - get(1)));
      }
      if (R == n) {
        ans = max(ans, abs(X + GL - get(n - 2)) - abs(GL - get(n - 2)));
      }
      L--;
      R--;
      L = max((long long)0, L - 1);
      R--;
      if (R == n - 2) R--;
      pair<long long, long long> p1 = split(base, L);
      pair<long long, long long> p2 = split(p1.second, R - L + 1);
      if (decart[p2.first].F) ans = 2 * X;
      if (decart[p2.first].S > INF) {
        ans = max(ans, 2 * (max((long long)0, X + decart[p2.first].S)));
      }
      ans = max(ans, 2 * X + decart[p2.first].T);
      if (X * 2 >= abs(decart[p2.first].G)) ans = max(ans, decart[p2.first].G);
      base = merg(p2.first, p2.second);
      base = merg(p1.first, base);
      cout << ans + G << endl;
    } else {
      long long L, R, X;
      cin >> L >> R >> X;
      if (L == 1)
        GF += X;
      else {
        G += abs(get(L - 1) + X - get(L - 2)) - abs(get(L - 1) - get(L - 2));
      }
      if (R == n)
        GL += X;
      else {
        G += abs(get(R - 1) + X - get(R)) - abs(get(R - 1) - get(R));
      }
      L--;
      R--;
      L = max((long long)0, L - 1);
      R--;
      if (R == n - 2) R--;
      pair<long long, long long> p1 = split(base, L);
      pair<long long, long long> p2 = split(p1.second, R - L + 1);
      P(p2.first, X);
      base = merg(p2.first, p2.second);
      base = merg(p1.first, base);
      Ch(L);
      Ch(R);
      if (L != 0) Ch(L - 1);
      if (R != n - 3) Ch(R + 1);
    }
  }
  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 INF = -1e18, GF, GL;
struct Vertex {
  long long l;
  long long r;
  long long pr;
  long long sz;
  long long value;
  long long p;
  bool F;
  long long S;
  long long T;
  bool f;
  long long s;
  long long t;
  long long g;
  long long G;
};
vector<Vertex> decart;
pair<long long, long long> SP = make_pair(-1, -1);
long long n, base;
void update(long long vertex) {
  if (vertex == -1) return;
  long long sz = 1, L = decart[vertex].l, R = decart[vertex].r;
  decart[vertex].F = decart[vertex].f;
  decart[vertex].S = decart[vertex].s;
  decart[vertex].T = decart[vertex].t;
  decart[vertex].G = decart[vertex].g;
  if (L != -1) {
    sz += decart[L].sz;
    decart[vertex].F |= decart[L].F;
    decart[vertex].S = max(decart[vertex].S, decart[L].S);
    decart[vertex].T = max(decart[vertex].T, decart[L].T);
    decart[vertex].G = max(decart[vertex].G, decart[L].G);
  }
  if (R != -1) {
    sz += decart[R].sz;
    decart[vertex].F |= decart[R].F;
    decart[vertex].S = max(decart[vertex].S, decart[R].S);
    decart[vertex].T = max(decart[vertex].T, decart[R].T);
    decart[vertex].G = max(decart[vertex].G, decart[R].G);
  }
  decart[vertex].sz = sz;
}
void push(long long vertex) {
  if (vertex == -1) return;
  long long pp = decart[vertex].p;
  decart[vertex].p = 0;
  if (decart[vertex].l != -1) {
    decart[decart[vertex].l].value += pp;
    decart[decart[vertex].l].p += pp;
  }
  if (decart[vertex].r != -1) {
    decart[decart[vertex].r].value += pp;
    decart[decart[vertex].r].p += pp;
  }
}
void P(long long vertex, long long wh) {
  push(vertex);
  decart[vertex].value += wh;
  decart[vertex].p += wh;
}
pair<long long, long long> split(long long father, long long number) {
  if (father == -1) return SP;
  push(father);
  long long l = 1;
  if (decart[father].l != -1) {
    l += decart[decart[father].l].sz;
  }
  if (l <= number) {
    pair<long long, long long> p = split(decart[father].r, number - l);
    decart[father].r = p.first;
    p.first = father;
    update(father);
    return p;
  }
  pair<long long, long long> p = split(decart[father].l, number);
  decart[father].l = p.second;
  p.second = father;
  update(father);
  return p;
}
long long merg(long long first, long long second) {
  push(first);
  push(second);
  if (first == -1) return second;
  if (second == -1) return first;
  if (decart[first].pr >= decart[second].pr) {
    long long v = merg(decart[first].r, second);
    decart[first].r = v;
    update(first);
    return first;
  }
  long long v = merg(first, decart[second].l);
  decart[second].l = v;
  update(second);
  return second;
}
void create(long long a, long long b, long long c) {
  Vertex v = {-1, -1, rand(), 1, b, 0};
  v.S = INF;
  v.T = INF;
  v.G = INF;
  if (b >= a && b >= c)
    v.F = true;
  else {
    v.F = false;
    if (b >= a || b >= c) {
      v.S = min(b - a, b - c);
    } else {
      v.T = 2 * (b - a + b - c);
      v.G = 2 * max(b - a, b - c);
    }
  }
  v.f = v.F;
  v.s = v.S;
  v.t = v.T;
  v.g = v.G;
  decart.push_back(v);
  base = merg(base, decart.size() - 1);
}
long long Get(long long vertex, long long sk) {
  push(vertex);
  long long L = decart[vertex].l;
  long long R = decart[vertex].r;
  if (L != -1) {
    long long sz = decart[L].sz;
    if (sz > sk) return Get(L, sk);
    sk -= sz;
  }
  if (sk == 0) return decart[vertex].value;
  return Get(R, sk - 1);
}
long long get(long long ind) {
  if (ind == 0) return GF;
  if (ind == n - 1) return GL;
  return Get(base, ind - 1);
}
void Ch(long long dind) {
  long long a = get(dind);
  long long b = get(dind + 1);
  long long c = get(dind + 2);
  pair<long long, long long> p1 = split(base, dind);
  pair<long long, long long> p2 = split(p1.second, 1);
  base = p1.first;
  create(a, b, c);
  base = merg(base, p2.second);
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  base = -1;
  cin >> n;
  vector<long long> v;
  for (long long i = 0; i < n; i++) {
    long long value;
    cin >> value;
    v.push_back(value);
  }
  GF = v[0];
  GL = v[n - 1];
  long long G = 0;
  for (long long i = 0; i < n - 1; i++) G += abs(v[i + 1] - v[i]);
  for (long long i = 1; i < n - 1; i++) {
    create(v[i - 1], v[i], v[i + 1]);
  }
  long long q;
  cin >> q;
  for (long long i = 0; i < q; i++) {
    long long t;
    cin >> t;
    if (t == 1) {
      long long L, R, X;
      cin >> L >> R >> X;
      long long ans = -2 * X;
      if (L == 1) {
        ans = max(ans, abs(X + GF - get(1)) - abs(GF - get(1)));
      }
      if (R == n) {
        ans = max(ans, abs(X + GL - get(n - 2)) - abs(GL - get(n - 2)));
      }
      L--;
      R--;
      L = max((long long)0, L - 1);
      R--;
      if (R == n - 2) R--;
      pair<long long, long long> p1 = split(base, L);
      pair<long long, long long> p2 = split(p1.second, R - L + 1);
      if (decart[p2.first].F) ans = 2 * X;
      if (decart[p2.first].S > INF) {
        ans = max(ans, 2 * (max((long long)0, X + decart[p2.first].S)));
      }
      ans = max(ans, 2 * X + decart[p2.first].T);
      if (X * 2 >= abs(decart[p2.first].G)) ans = max(ans, decart[p2.first].G);
      base = merg(p2.first, p2.second);
      base = merg(p1.first, base);
      cout << ans + G << endl;
    } else {
      long long L, R, X;
      cin >> L >> R >> X;
      if (L == 1)
        GF += X;
      else {
        G += abs(get(L - 1) + X - get(L - 2)) - abs(get(L - 1) - get(L - 2));
      }
      if (R == n)
        GL += X;
      else {
        G += abs(get(R - 1) + X - get(R)) - abs(get(R - 1) - get(R));
      }
      L--;
      R--;
      L = max((long long)0, L - 1);
      R--;
      if (R == n - 2) R--;
      pair<long long, long long> p1 = split(base, L);
      pair<long long, long long> p2 = split(p1.second, R - L + 1);
      P(p2.first, X);
      base = merg(p2.first, p2.second);
      base = merg(p1.first, base);
      Ch(L);
      Ch(R);
      if (L != 0) Ch(L - 1);
      if (R != n - 3) Ch(R + 1);
    }
  }
  return 0;
}

```