#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x) {
  char c;
  bool nega = 0;
  while ((!isdigit(c = getchar())) && (c != '-'))
    ;
  if (c == '-') {
    nega = 1;
    c = getchar();
  }
  x = c - 48;
  while (isdigit(c = getchar())) x = x * 10 + c - 48;
  if (nega) x = -x;
}
template <typename T>
inline void writep(T x) {
  if (x > 9) writep(x / 10);
  putchar(x % 10 + 48);
}
template <typename T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  writep(x);
}
template <typename T>
inline void writeln(T x) {
  write(x);
  putchar('\n');
}
class segment_tree {
 public:
  static const int SUM = 0;
  static const int MIN = 1;
  static const int MAX = 2;
  static inline long long sum(long long a, long long b) { return a + b; }
  static inline long long min(long long a, long long b) {
    return (a < b) ? a : b;
  }
  static inline long long max(long long a, long long b) {
    return (a > b) ? a : b;
  }
  typedef segment_tree *iterator;
  int l, r, m;
  long long value, lazy;
  iterator left, right;
  long long (*func)(long long, long long);
  segment_tree(long long *a, int l, int r, int type) {
    if (type == SUM)
      func = sum;
    else if (type == MIN)
      func = min;
    else
      func = max;
    this->l = l;
    this->r = r;
    m = (l + r) / 2;
    lazy = 0;
    value = (type == MIN) ? 1e18 : 0;
    left = right = nullptr;
    if (l == r)
      value = a[l];
    else {
      left = new segment_tree(a, l, m, type);
      right = new segment_tree(a, m + 1, r, type);
      value = func(left->value, right->value);
    }
  }
  void down() {
    left->value += lazy;
    left->lazy += lazy;
    right->value += lazy;
    right->lazy += lazy;
    lazy = 0;
  }
  void add(int u, int v, long long x) {
    if (l > v || r < u) return;
    if (u <= l && v >= r) {
      value += x;
      lazy += x;
    } else {
      down();
      left->add(u, v, x);
      right->add(u, v, x);
      value = func(left->value, right->value);
    }
  }
  void set(int u, long long x) {
    if (l == r)
      value = x;
    else {
      down();
      if (m >= u)
        left->set(u, x);
      else
        right->set(u, x);
      value = func(left->value, right->value);
    }
  }
  long long get(int u, int v) {
    if (l > v || r < u) return (func == min) ? 1e18 : 0;
    if (u <= l && v >= r) return value;
    down();
    return min(left->get(u, v), right->get(u, v));
  }
  long long get(int u) {
    if (l == r) return value;
    down();
    if (m >= u)
      return left->get(u);
    else
      return right->get(u);
  }
};
segment_tree::iterator tree_a, tree_f, tree_s;
int n, q;
long long a[100001];
long long s[100001];
long long f[100001];
void up(int i) {
  if (i > 1 && i < n)
    tree_s->set(i,
                max(tree_a->get(i - 1), tree_a->get(i + 1)) - tree_a->get(i));
}
int main() {
  read(n);
  for (int i = (1); i <= (n); i++) read(a[i]);
  for (int i = (1); i < (n); i++) f[i] = abs(a[i] - a[i + 1]);
  for (int i = (2); i < (n); i++) s[i] = max(a[i - 1], a[i + 1]) - a[i];
  tree_a = new segment_tree(a, 1, n, segment_tree::MIN);
  tree_f = new segment_tree(f, 1, n - 1, segment_tree::SUM);
  tree_s = new segment_tree(s, 2, n - 1, segment_tree::MIN);
  read(q);
  {
    int t, l, r, L, R, m, p;
    long long ans, x, al, ar, temp, ta, am;
    for (int i = (1); i <= (q); i++) {
      read(t);
      read(l);
      read(r);
      read(x);
      if (t == 1) {
        ans = 0;
        if (l == 1) {
          al = tree_a->get(l, l);
          temp = tree_a->get(l + 1, l + 1);
          ans = max(
              ans, tree_f->get(1, n - 1) - abs(al - temp) + abs(al + x - temp));
          l = 2;
        }
        if (r == n) {
          ar = tree_a->get(r, r);
          temp = tree_a->get(r - 1, r - 1);
          ans = max(
              ans, tree_f->get(1, n - 1) - abs(ar - temp) + abs(ar + x - temp));
          r = n - 1;
        }
        if (l > r) goto line0;
        if (l == r) {
          ta = tree_f->get(1, n - 1);
          al = tree_a->get(l);
          if (l > 1) {
            temp = tree_a->get(l - 1);
            ta = ta - abs(al - temp) + abs(al + x - temp);
          }
          if (r < n) {
            temp = tree_a->get(r + 1);
            ta = ta - abs(al - temp) + abs(al + x - temp);
          }
          ans = max(ans, ta);
        } else {
          temp = tree_s->get(l, r);
          if (temp <= 0)
            ans = tree_f->get(1, n - 1) + x * 2;
          else {
            L = l;
            R = r;
            am = tree_a->get(l, r);
            while (L <= R) {
              m = (L + R) / 2;
              if (tree_a->get(l, m) == am) {
                p = m;
                R = m - 1;
              } else
                L = m + 1;
            }
            ta = tree_f->get(1, n - 1);
            al = tree_a->get(p);
            temp = tree_a->get(p - 1);
            ta = ta - abs(al - temp) + abs(al + x - temp);
            temp = tree_a->get(p + 1);
            ta = ta - abs(al - temp) + abs(al + x - temp);
            ans = max(ans, ta);
            if (p > l) {
              temp = tree_s->get(l, p - 1);
              ans = max(ans,
                        tree_f->get(1, n - 1) + x - abs(temp) + abs(temp - x));
            }
            if (p < r) {
              temp = tree_s->get(p + 1, r);
              ans = max(ans,
                        tree_f->get(1, n - 1) + x - abs(temp) + abs(temp - x));
            }
          }
        }
      line0:;
        writeln(ans);
      } else {
        tree_a->add(l, r, x);
        up(l);
        up(r);
        up(l - 1);
        up(r + 1);
        if (l > 1) tree_f->set(l - 1, abs(tree_a->get(l) - tree_a->get(l - 1)));
        if (r < n) tree_f->set(r, abs(tree_a->get(r) - tree_a->get(r + 1)));
      }
    }
  }
}

### Prompt

Please formulate a CPP solution 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;
template <typename T>
inline void read(T &x) {
  char c;
  bool nega = 0;
  while ((!isdigit(c = getchar())) && (c != '-'))
    ;
  if (c == '-') {
    nega = 1;
    c = getchar();
  }
  x = c - 48;
  while (isdigit(c = getchar())) x = x * 10 + c - 48;
  if (nega) x = -x;
}
template <typename T>
inline void writep(T x) {
  if (x > 9) writep(x / 10);
  putchar(x % 10 + 48);
}
template <typename T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  writep(x);
}
template <typename T>
inline void writeln(T x) {
  write(x);
  putchar('\n');
}
class segment_tree {
 public:
  static const int SUM = 0;
  static const int MIN = 1;
  static const int MAX = 2;
  static inline long long sum(long long a, long long b) { return a + b; }
  static inline long long min(long long a, long long b) {
    return (a < b) ? a : b;
  }
  static inline long long max(long long a, long long b) {
    return (a > b) ? a : b;
  }
  typedef segment_tree *iterator;
  int l, r, m;
  long long value, lazy;
  iterator left, right;
  long long (*func)(long long, long long);
  segment_tree(long long *a, int l, int r, int type) {
    if (type == SUM)
      func = sum;
    else if (type == MIN)
      func = min;
    else
      func = max;
    this->l = l;
    this->r = r;
    m = (l + r) / 2;
    lazy = 0;
    value = (type == MIN) ? 1e18 : 0;
    left = right = nullptr;
    if (l == r)
      value = a[l];
    else {
      left = new segment_tree(a, l, m, type);
      right = new segment_tree(a, m + 1, r, type);
      value = func(left->value, right->value);
    }
  }
  void down() {
    left->value += lazy;
    left->lazy += lazy;
    right->value += lazy;
    right->lazy += lazy;
    lazy = 0;
  }
  void add(int u, int v, long long x) {
    if (l > v || r < u) return;
    if (u <= l && v >= r) {
      value += x;
      lazy += x;
    } else {
      down();
      left->add(u, v, x);
      right->add(u, v, x);
      value = func(left->value, right->value);
    }
  }
  void set(int u, long long x) {
    if (l == r)
      value = x;
    else {
      down();
      if (m >= u)
        left->set(u, x);
      else
        right->set(u, x);
      value = func(left->value, right->value);
    }
  }
  long long get(int u, int v) {
    if (l > v || r < u) return (func == min) ? 1e18 : 0;
    if (u <= l && v >= r) return value;
    down();
    return min(left->get(u, v), right->get(u, v));
  }
  long long get(int u) {
    if (l == r) return value;
    down();
    if (m >= u)
      return left->get(u);
    else
      return right->get(u);
  }
};
segment_tree::iterator tree_a, tree_f, tree_s;
int n, q;
long long a[100001];
long long s[100001];
long long f[100001];
void up(int i) {
  if (i > 1 && i < n)
    tree_s->set(i,
                max(tree_a->get(i - 1), tree_a->get(i + 1)) - tree_a->get(i));
}
int main() {
  read(n);
  for (int i = (1); i <= (n); i++) read(a[i]);
  for (int i = (1); i < (n); i++) f[i] = abs(a[i] - a[i + 1]);
  for (int i = (2); i < (n); i++) s[i] = max(a[i - 1], a[i + 1]) - a[i];
  tree_a = new segment_tree(a, 1, n, segment_tree::MIN);
  tree_f = new segment_tree(f, 1, n - 1, segment_tree::SUM);
  tree_s = new segment_tree(s, 2, n - 1, segment_tree::MIN);
  read(q);
  {
    int t, l, r, L, R, m, p;
    long long ans, x, al, ar, temp, ta, am;
    for (int i = (1); i <= (q); i++) {
      read(t);
      read(l);
      read(r);
      read(x);
      if (t == 1) {
        ans = 0;
        if (l == 1) {
          al = tree_a->get(l, l);
          temp = tree_a->get(l + 1, l + 1);
          ans = max(
              ans, tree_f->get(1, n - 1) - abs(al - temp) + abs(al + x - temp));
          l = 2;
        }
        if (r == n) {
          ar = tree_a->get(r, r);
          temp = tree_a->get(r - 1, r - 1);
          ans = max(
              ans, tree_f->get(1, n - 1) - abs(ar - temp) + abs(ar + x - temp));
          r = n - 1;
        }
        if (l > r) goto line0;
        if (l == r) {
          ta = tree_f->get(1, n - 1);
          al = tree_a->get(l);
          if (l > 1) {
            temp = tree_a->get(l - 1);
            ta = ta - abs(al - temp) + abs(al + x - temp);
          }
          if (r < n) {
            temp = tree_a->get(r + 1);
            ta = ta - abs(al - temp) + abs(al + x - temp);
          }
          ans = max(ans, ta);
        } else {
          temp = tree_s->get(l, r);
          if (temp <= 0)
            ans = tree_f->get(1, n - 1) + x * 2;
          else {
            L = l;
            R = r;
            am = tree_a->get(l, r);
            while (L <= R) {
              m = (L + R) / 2;
              if (tree_a->get(l, m) == am) {
                p = m;
                R = m - 1;
              } else
                L = m + 1;
            }
            ta = tree_f->get(1, n - 1);
            al = tree_a->get(p);
            temp = tree_a->get(p - 1);
            ta = ta - abs(al - temp) + abs(al + x - temp);
            temp = tree_a->get(p + 1);
            ta = ta - abs(al - temp) + abs(al + x - temp);
            ans = max(ans, ta);
            if (p > l) {
              temp = tree_s->get(l, p - 1);
              ans = max(ans,
                        tree_f->get(1, n - 1) + x - abs(temp) + abs(temp - x));
            }
            if (p < r) {
              temp = tree_s->get(p + 1, r);
              ans = max(ans,
                        tree_f->get(1, n - 1) + x - abs(temp) + abs(temp - x));
            }
          }
        }
      line0:;
        writeln(ans);
      } else {
        tree_a->add(l, r, x);
        up(l);
        up(r);
        up(l - 1);
        up(r + 1);
        if (l > 1) tree_f->set(l - 1, abs(tree_a->get(l) - tree_a->get(l - 1)));
        if (r < n) tree_f->set(r, abs(tree_a->get(r) - tree_a->get(r + 1)));
      }
    }
  }
}

```