#include <bits/stdc++.h>
using namespace std;
const int maxn = 100099;
const long long inf = 0x7f7f7f7f7f7f7f7fll;
int n, q;
long long a[100100];
long long snow(const long long &);
void maxupd(int &p, int q, int r) {
  if (a[q] > a[r])
    p = q;
  else
    p = r;
}
void minupd(int &p, int q, int r) {
  if (a[q] < a[r])
    p = q;
  else
    p = r;
}
struct node {
  long long asum;
  int l, r, m1, m0, sta, sep;
  node *lht, *rht;
  node(int il = 0, int ir = 0)
      : asum(0ll),
        l(il),
        r(ir),
        m1(0),
        m0(maxn),
        sta(0),
        sep(0),
        lht(0),
        rht(0) {}
  void upd() {
    asum = lht->asum + rht->asum;
    if (lht->sta == 2 && rht->sta == 1)
      sta = 4, sep = lht->r;
    else if (lht->sta == 4 && rht->sta == 1)
      sta = 4, sep = lht->sep;
    else if (lht->sta == 2 && rht->sta == 4)
      sta = 4, sep = rht->sep;
    else if (lht->sta == 1 && rht->sta == 1)
      sta = 1, sep = 0;
    else if (lht->sta == 2 && rht->sta == 2)
      sta = 2, sep = 0;
    else
      sta = 3, sep = 0;
    maxupd(m1, lht->m1, rht->m1);
    minupd(m0, lht->m0, rht->m0);
  }
  void modify(int p, int v) {
    if (l == r) {
      a[l] += v;
      if (a[l] >= 0) {
        sta = 1;
        sep = 0;
        m0 = l;
        m1 = 0;
      } else {
        sta = 2;
        sep = 0;
        m1 = l;
        m0 = maxn;
      }
      asum = snow(a[l]);
    } else {
      int m = lht->r;
      if (p <= m)
        lht->modify(p, v);
      else
        rht->modify(p, v);
      upd();
    }
  }
  int getsta(int ql, int qr, int &qs) {
    if (l == ql && r == qr) {
      if (sta == 4) qs = sep;
      return sta;
    }
    int m = lht->r;
    if (qr <= m) return lht->getsta(ql, qr, qs);
    if (ql > m) return rht->getsta(ql, qr, qs);
    int ls = lht->getsta(ql, m, qs), rs = rht->getsta(m + 1, qr, qs);
    if (ls == 2 && rs == 1) {
      qs = m;
      return 4;
    } else if ((ls == 4 && rs == 1) || (ls == 2 && rs == 4))
      return 4;
    else if (ls == 1 && rs == 1)
      return 1;
    else if (ls == 2 && rs == 2)
      return 2;
    else
      return 3;
  }
  int getm0(int ql, int qr) {
    if (l == ql && r == qr) return m0;
    int m = lht->r;
    if (qr <= m) return lht->getm0(ql, qr);
    if (ql > m) return rht->getm0(ql, qr);
    int l0 = lht->getm0(ql, m), r0 = rht->getm0(m + 1, qr);
    return a[l0] < a[r0] ? l0 : r0;
  }
  int getm1(int ql, int qr) {
    if (l == ql && r == qr) return m1;
    int m = lht->r;
    if (qr <= m) return lht->getm1(ql, qr);
    if (ql > m) return rht->getm1(ql, qr);
    int l1 = lht->getm1(ql, m), r1 = rht->getm1(m + 1, qr);
    return a[l1] > a[r1] ? l1 : r1;
  }
} * root;
void sread() {
  scanf("%d", &n);
  for (int i = 1, __yukii__ = n; i <= __yukii__; ++i) scanf("%I64d", a + i);
  for (int i = n, __yui__ = 1; i >= __yui__; --i) a[i] -= a[i - 1];
  a[0] = -inf;
  a[maxn] = inf;
  scanf("%d", &q);
}
long long snow(const long long &x) { return x < 0 ? -x : x; }
node *mktree(int l, int r) {
  node *ans = new node(l, r);
  if (l == r) {
    if (a[l] >= 0) {
      ans->sta = 1;
      ans->m0 = l;
    } else {
      ans->sta = 2;
      ans->m1 = l;
    }
    ans->asum = snow(a[l]);
  } else {
    int m = l + ((r - l) >> 1);
    ans->lht = mktree(l, m);
    ans->rht = mktree(m + 1, r);
    ans->upd();
  }
  return ans;
}
long long query(int l, int r, int x) {
  long long ans = root->asum - snow(a[1]);
  if (l == r++)
    return ans + snow(a[l] + x) - snow(a[l]) + snow(a[l + 1] - x) -
           snow(a[l + 1]);
  int sep, t1, t2;
  int sta = root->getsta(l, r, sep);
  switch (sta) {
    case 1:
      sep = root->getm0(l + 1, r);
      return ans + x + snow(x - a[sep]) - a[sep];
    case 2:
      sep = root->getm1(l, r - 1);
      return ans + x + snow(x + a[sep]) + a[sep];
    case 3:
      return ans + (x << 1);
    case 4:
      if (l != sep) t1 = root->getm1(l, sep - 1);
      if (r != sep + 1) t2 = root->getm0(sep + 2, r);
      return ans + max(max(snow(x + a[sep]) + a[sep] + snow(x - a[sep + 1]) -
                               a[sep + 1],
                           r == sep + 1 ? -0x1f1f1f1f1f1f1f1fll
                                        : x + snow(x - a[t2]) - a[t2]),
                       l == sep ? -0x1f1f1f1f1f1f1f1fll
                                : snow(x + a[t1]) + a[t1] + x);
  }
}
int main(int argc, char **argv) {
  sread();
  root = mktree(1, n);
  int t, l, r, x;
  while (q--) {
    scanf("%d%d%d%d", &t, &l, &r, &x);
    if (t == 1)
      printf("%I64d\n", query(l, r, x));
    else {
      root->modify(l, x);
      if (r < n) root->modify(r + 1, -x);
    }
  }
  return 0;
}

### 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 maxn = 100099;
const long long inf = 0x7f7f7f7f7f7f7f7fll;
int n, q;
long long a[100100];
long long snow(const long long &);
void maxupd(int &p, int q, int r) {
  if (a[q] > a[r])
    p = q;
  else
    p = r;
}
void minupd(int &p, int q, int r) {
  if (a[q] < a[r])
    p = q;
  else
    p = r;
}
struct node {
  long long asum;
  int l, r, m1, m0, sta, sep;
  node *lht, *rht;
  node(int il = 0, int ir = 0)
      : asum(0ll),
        l(il),
        r(ir),
        m1(0),
        m0(maxn),
        sta(0),
        sep(0),
        lht(0),
        rht(0) {}
  void upd() {
    asum = lht->asum + rht->asum;
    if (lht->sta == 2 && rht->sta == 1)
      sta = 4, sep = lht->r;
    else if (lht->sta == 4 && rht->sta == 1)
      sta = 4, sep = lht->sep;
    else if (lht->sta == 2 && rht->sta == 4)
      sta = 4, sep = rht->sep;
    else if (lht->sta == 1 && rht->sta == 1)
      sta = 1, sep = 0;
    else if (lht->sta == 2 && rht->sta == 2)
      sta = 2, sep = 0;
    else
      sta = 3, sep = 0;
    maxupd(m1, lht->m1, rht->m1);
    minupd(m0, lht->m0, rht->m0);
  }
  void modify(int p, int v) {
    if (l == r) {
      a[l] += v;
      if (a[l] >= 0) {
        sta = 1;
        sep = 0;
        m0 = l;
        m1 = 0;
      } else {
        sta = 2;
        sep = 0;
        m1 = l;
        m0 = maxn;
      }
      asum = snow(a[l]);
    } else {
      int m = lht->r;
      if (p <= m)
        lht->modify(p, v);
      else
        rht->modify(p, v);
      upd();
    }
  }
  int getsta(int ql, int qr, int &qs) {
    if (l == ql && r == qr) {
      if (sta == 4) qs = sep;
      return sta;
    }
    int m = lht->r;
    if (qr <= m) return lht->getsta(ql, qr, qs);
    if (ql > m) return rht->getsta(ql, qr, qs);
    int ls = lht->getsta(ql, m, qs), rs = rht->getsta(m + 1, qr, qs);
    if (ls == 2 && rs == 1) {
      qs = m;
      return 4;
    } else if ((ls == 4 && rs == 1) || (ls == 2 && rs == 4))
      return 4;
    else if (ls == 1 && rs == 1)
      return 1;
    else if (ls == 2 && rs == 2)
      return 2;
    else
      return 3;
  }
  int getm0(int ql, int qr) {
    if (l == ql && r == qr) return m0;
    int m = lht->r;
    if (qr <= m) return lht->getm0(ql, qr);
    if (ql > m) return rht->getm0(ql, qr);
    int l0 = lht->getm0(ql, m), r0 = rht->getm0(m + 1, qr);
    return a[l0] < a[r0] ? l0 : r0;
  }
  int getm1(int ql, int qr) {
    if (l == ql && r == qr) return m1;
    int m = lht->r;
    if (qr <= m) return lht->getm1(ql, qr);
    if (ql > m) return rht->getm1(ql, qr);
    int l1 = lht->getm1(ql, m), r1 = rht->getm1(m + 1, qr);
    return a[l1] > a[r1] ? l1 : r1;
  }
} * root;
void sread() {
  scanf("%d", &n);
  for (int i = 1, __yukii__ = n; i <= __yukii__; ++i) scanf("%I64d", a + i);
  for (int i = n, __yui__ = 1; i >= __yui__; --i) a[i] -= a[i - 1];
  a[0] = -inf;
  a[maxn] = inf;
  scanf("%d", &q);
}
long long snow(const long long &x) { return x < 0 ? -x : x; }
node *mktree(int l, int r) {
  node *ans = new node(l, r);
  if (l == r) {
    if (a[l] >= 0) {
      ans->sta = 1;
      ans->m0 = l;
    } else {
      ans->sta = 2;
      ans->m1 = l;
    }
    ans->asum = snow(a[l]);
  } else {
    int m = l + ((r - l) >> 1);
    ans->lht = mktree(l, m);
    ans->rht = mktree(m + 1, r);
    ans->upd();
  }
  return ans;
}
long long query(int l, int r, int x) {
  long long ans = root->asum - snow(a[1]);
  if (l == r++)
    return ans + snow(a[l] + x) - snow(a[l]) + snow(a[l + 1] - x) -
           snow(a[l + 1]);
  int sep, t1, t2;
  int sta = root->getsta(l, r, sep);
  switch (sta) {
    case 1:
      sep = root->getm0(l + 1, r);
      return ans + x + snow(x - a[sep]) - a[sep];
    case 2:
      sep = root->getm1(l, r - 1);
      return ans + x + snow(x + a[sep]) + a[sep];
    case 3:
      return ans + (x << 1);
    case 4:
      if (l != sep) t1 = root->getm1(l, sep - 1);
      if (r != sep + 1) t2 = root->getm0(sep + 2, r);
      return ans + max(max(snow(x + a[sep]) + a[sep] + snow(x - a[sep + 1]) -
                               a[sep + 1],
                           r == sep + 1 ? -0x1f1f1f1f1f1f1f1fll
                                        : x + snow(x - a[t2]) - a[t2]),
                       l == sep ? -0x1f1f1f1f1f1f1f1fll
                                : snow(x + a[t1]) + a[t1] + x);
  }
}
int main(int argc, char **argv) {
  sread();
  root = mktree(1, n);
  int t, l, r, x;
  while (q--) {
    scanf("%d%d%d%d", &t, &l, &r, &x);
    if (t == 1)
      printf("%I64d\n", query(l, r, x));
    else {
      root->modify(l, x);
      if (r < n) root->modify(r + 1, -x);
    }
  }
  return 0;
}

```