#include <bits/stdc++.h>
const int inf = 0x3f3f3f3f, Inf = 0x7fffffff;
const long long INF = 1e18;
const double eps = 1e-10;
unsigned int seed = 19260817;
const unsigned int _RAND_MAX_ = 4294967295u;
__inline__ __attribute__((always_inline)) unsigned int Rand() {
  return seed = seed * 998244353u + 1000000007u;
}
template <typename _Tp>
_Tp gcd(const _Tp &a, const _Tp &b) {
  return (!b) ? a : gcd(b, a % b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp abs(const _Tp &a) {
  return a > 0 ? a : -a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp max(const _Tp &a, const _Tp &b) {
  return a < b ? b : a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp min(const _Tp &a, const _Tp &b) {
  return a < b ? a : b;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmax(_Tp &a, const _Tp &b) {
  (a < b) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmin(_Tp &a, const _Tp &b) {
  (a > b) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) bool _cmp(const _Tp &a,
                                                    const _Tp &b) {
  return abs(a - b) <= eps;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void read(_Tp &x) {
  register char ch(getchar());
  bool f(false);
  while (ch < 48 || ch > 57) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (ch >= 48 && ch <= 57)
    x = (((x << 2) + x) << 1) + (ch & 15), ch = getchar();
  if (f) x = -x;
}
template <typename _Tp, typename... Args>
__inline__ __attribute__((always_inline)) void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
__inline__ __attribute__((always_inline)) int read_str(char *s) {
  register char ch(getchar());
  while (ch == ' ' || ch == '\r' || ch == '\n') ch = getchar();
  register char *tar = s;
  *tar = ch, ch = getchar();
  while (ch != ' ' && ch != '\r' && ch != '\n' && ch != EOF)
    *(++tar) = ch, ch = getchar();
  return tar - s + 1;
}
const int N = 100005;
struct Pair {
  long long left, right;
} b[N];
long long a[N];
struct seg_tr {
  struct Node {
    int ls, rs;
    long long maxx;
    __inline__ __attribute__((always_inline)) Node() : maxx(-INF) {}
  } f[N << 1];
  int node_cnt;
  __inline__ __attribute__((always_inline)) void PushUp(const int &x) {
    f[x].maxx = max(f[f[x].ls].maxx, f[f[x].rs].maxx);
  }
  int build(const int &l, const int &r) {
    int cur = ++node_cnt;
    if (l == r) {
      f[cur].maxx = min(b[l].left, 0ll) + min(b[l].right, 0ll);
      return cur;
    }
    int mid = (l + r) >> 1;
    f[cur].ls = build(l, mid);
    f[cur].rs = build(mid + 1, r);
    PushUp(cur);
    return cur;
  }
  void Update(const int &pos, const int &l, const int &r, const int &cur,
              const Pair &val) {
    if (l == r) {
      f[cur].maxx = min(val.left, 0ll) + min(val.right, 0ll);
      return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
      Update(pos, l, mid, f[cur].ls, val);
    else
      Update(pos, mid + 1, r, f[cur].rs, val);
    PushUp(cur);
  }
  long long Query(const int &L, const int &R, const int &l, const int &r,
                  const int &cur) {
    if (L <= l && r <= R) {
      return f[cur].maxx;
    }
    int mid = (l + r) >> 1;
    return max(L <= mid ? Query(L, R, l, mid, f[cur].ls) : -INF,
               R > mid ? Query(L, R, mid + 1, r, f[cur].rs) : -INF);
  }
} tr;
int main() {
  int n;
  read(n);
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
  }
  for (int i = 2; i <= n; ++i) {
    ans += abs(a[i] - a[i - 1]);
  }
  for (int i = 1; i <= n; ++i) {
    b[i].left = a[i] - a[i - 1];
    b[i].right = a[i] - a[i + 1];
  }
  b[1].left = -inf, b[n].right = -inf;
  int root = tr.build(1, n);
  int _;
  long long tmp;
  read(_);
  int opt, l, r;
  long long x;
  while (_--) {
    read(opt, l, r, x);
    if (opt == 1) {
      if (l != r) {
        long long t = -INF;
        if (l == 1) {
          chmax(t, -abs(b[1].right) + abs(b[1].right + x));
          ++l;
        }
        if (r == n) {
          chmax(t, -abs(b[n].left) + abs(b[n].left + x));
          --r;
        }
        tmp = tr.Query(l, r, 1, n, root);
        if (tmp == 0) {
          printf("%lld\n", ans + max(t, (x << 1)));
        } else {
          printf("%lld\n", ans + max(t, x + 2 * max(-x, tmp) + x));
        }
      } else {
        if (l == 1) {
          printf("%lld\n", ans - abs(b[1].right) + abs(b[1].right + x));
        } else if (r == n) {
          printf("%lld\n", ans - abs(b[n].left) + abs(b[n].left + x));
        } else {
          printf("%lld\n", ans + abs(b[l].left + x) + abs(b[l].right + x) -
                               abs(b[l].left) - abs(b[l].right));
        }
      }
    } else {
      if (l > 1) {
        ans += -abs(b[l].left) + abs(b[l].left + x);
      }
      if (r < n) {
        ans += -abs(b[r].right) + abs(b[r].right + x);
      }
      b[l].left += x;
      b[l - 1].right -= x;
      b[r].right += x;
      b[r + 1].left -= x;
      tr.Update(l, 1, n, root, b[l]);
      if (l > 1) tr.Update(l - 1, 1, n, root, b[l - 1]);
      tr.Update(r, 1, n, root, b[r]);
      if (r < n) tr.Update(r + 1, 1, n, root, b[r + 1]);
    }
  }
  return 0;
}

### Prompt

Generate 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>
const int inf = 0x3f3f3f3f, Inf = 0x7fffffff;
const long long INF = 1e18;
const double eps = 1e-10;
unsigned int seed = 19260817;
const unsigned int _RAND_MAX_ = 4294967295u;
__inline__ __attribute__((always_inline)) unsigned int Rand() {
  return seed = seed * 998244353u + 1000000007u;
}
template <typename _Tp>
_Tp gcd(const _Tp &a, const _Tp &b) {
  return (!b) ? a : gcd(b, a % b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp abs(const _Tp &a) {
  return a > 0 ? a : -a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp max(const _Tp &a, const _Tp &b) {
  return a < b ? b : a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp min(const _Tp &a, const _Tp &b) {
  return a < b ? a : b;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmax(_Tp &a, const _Tp &b) {
  (a < b) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmin(_Tp &a, const _Tp &b) {
  (a > b) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) bool _cmp(const _Tp &a,
                                                    const _Tp &b) {
  return abs(a - b) <= eps;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void read(_Tp &x) {
  register char ch(getchar());
  bool f(false);
  while (ch < 48 || ch > 57) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (ch >= 48 && ch <= 57)
    x = (((x << 2) + x) << 1) + (ch & 15), ch = getchar();
  if (f) x = -x;
}
template <typename _Tp, typename... Args>
__inline__ __attribute__((always_inline)) void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
__inline__ __attribute__((always_inline)) int read_str(char *s) {
  register char ch(getchar());
  while (ch == ' ' || ch == '\r' || ch == '\n') ch = getchar();
  register char *tar = s;
  *tar = ch, ch = getchar();
  while (ch != ' ' && ch != '\r' && ch != '\n' && ch != EOF)
    *(++tar) = ch, ch = getchar();
  return tar - s + 1;
}
const int N = 100005;
struct Pair {
  long long left, right;
} b[N];
long long a[N];
struct seg_tr {
  struct Node {
    int ls, rs;
    long long maxx;
    __inline__ __attribute__((always_inline)) Node() : maxx(-INF) {}
  } f[N << 1];
  int node_cnt;
  __inline__ __attribute__((always_inline)) void PushUp(const int &x) {
    f[x].maxx = max(f[f[x].ls].maxx, f[f[x].rs].maxx);
  }
  int build(const int &l, const int &r) {
    int cur = ++node_cnt;
    if (l == r) {
      f[cur].maxx = min(b[l].left, 0ll) + min(b[l].right, 0ll);
      return cur;
    }
    int mid = (l + r) >> 1;
    f[cur].ls = build(l, mid);
    f[cur].rs = build(mid + 1, r);
    PushUp(cur);
    return cur;
  }
  void Update(const int &pos, const int &l, const int &r, const int &cur,
              const Pair &val) {
    if (l == r) {
      f[cur].maxx = min(val.left, 0ll) + min(val.right, 0ll);
      return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
      Update(pos, l, mid, f[cur].ls, val);
    else
      Update(pos, mid + 1, r, f[cur].rs, val);
    PushUp(cur);
  }
  long long Query(const int &L, const int &R, const int &l, const int &r,
                  const int &cur) {
    if (L <= l && r <= R) {
      return f[cur].maxx;
    }
    int mid = (l + r) >> 1;
    return max(L <= mid ? Query(L, R, l, mid, f[cur].ls) : -INF,
               R > mid ? Query(L, R, mid + 1, r, f[cur].rs) : -INF);
  }
} tr;
int main() {
  int n;
  read(n);
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
  }
  for (int i = 2; i <= n; ++i) {
    ans += abs(a[i] - a[i - 1]);
  }
  for (int i = 1; i <= n; ++i) {
    b[i].left = a[i] - a[i - 1];
    b[i].right = a[i] - a[i + 1];
  }
  b[1].left = -inf, b[n].right = -inf;
  int root = tr.build(1, n);
  int _;
  long long tmp;
  read(_);
  int opt, l, r;
  long long x;
  while (_--) {
    read(opt, l, r, x);
    if (opt == 1) {
      if (l != r) {
        long long t = -INF;
        if (l == 1) {
          chmax(t, -abs(b[1].right) + abs(b[1].right + x));
          ++l;
        }
        if (r == n) {
          chmax(t, -abs(b[n].left) + abs(b[n].left + x));
          --r;
        }
        tmp = tr.Query(l, r, 1, n, root);
        if (tmp == 0) {
          printf("%lld\n", ans + max(t, (x << 1)));
        } else {
          printf("%lld\n", ans + max(t, x + 2 * max(-x, tmp) + x));
        }
      } else {
        if (l == 1) {
          printf("%lld\n", ans - abs(b[1].right) + abs(b[1].right + x));
        } else if (r == n) {
          printf("%lld\n", ans - abs(b[n].left) + abs(b[n].left + x));
        } else {
          printf("%lld\n", ans + abs(b[l].left + x) + abs(b[l].right + x) -
                               abs(b[l].left) - abs(b[l].right));
        }
      }
    } else {
      if (l > 1) {
        ans += -abs(b[l].left) + abs(b[l].left + x);
      }
      if (r < n) {
        ans += -abs(b[r].right) + abs(b[r].right + x);
      }
      b[l].left += x;
      b[l - 1].right -= x;
      b[r].right += x;
      b[r + 1].left -= x;
      tr.Update(l, 1, n, root, b[l]);
      if (l > 1) tr.Update(l - 1, 1, n, root, b[l - 1]);
      tr.Update(r, 1, n, root, b[r]);
      if (r < n) tr.Update(r + 1, 1, n, root, b[r + 1]);
    }
  }
  return 0;
}

```