Yaroslav has n points that lie on the Ox axis. The coordinate of the first point is x1, the coordinate of the second point is x2, ..., the coordinate of the n-th point is — xn. Now Yaroslav wants to execute m queries, each of them is of one of the two following types:

  1. Move the pj-th point from position xpj to position xpj + dj. At that, it is guaranteed that after executing such query all coordinates of the points will be distinct. 
  2. Count the sum of distances between all pairs of points that lie on the segment [lj, rj] (lj ≤ rj). In other words, you should count the sum of: <image>. 



Help Yaroslav.

Input

The first line contains integer n — the number of points (1 ≤ n ≤ 105). The second line contains distinct integers x1, x2, ..., xn — the coordinates of points (|xi| ≤ 109).

The third line contains integer m — the number of queries (1 ≤ m ≤ 105). The next m lines contain the queries. The j-th line first contains integer tj (1 ≤ tj ≤ 2) — the query type. If tj = 1, then it is followed by two integers pj and dj (1 ≤ pj ≤ n, |dj| ≤ 1000). If tj = 2, then it is followed by two integers lj and rj ( - 109 ≤ lj ≤ rj ≤ 109).

It is guaranteed that at any moment all the points have distinct coordinates.

Output

For each type 2 query print the answer on a single line. Print the answers in the order, in which the queries follow in the input.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams of the %I64d specifier.

Examples

Input

8
36 50 28 -75 40 -60 -95 -48
20
2 -61 29
1 5 -53
1 1 429
1 5 130
2 -101 -71
2 -69 53
1 1 404
1 5 518
2 -101 53
2 50 872
1 1 -207
2 -99 -40
1 7 -389
1 6 -171
1 2 464
1 7 -707
1 1 -730
1 1 560
2 635 644
1 7 -677


Output

176
20
406
1046
1638
156
0
#include <bits/stdc++.h>
using namespace std;
const int NR = 2e5 + 10;
void Min(int& x, int y) { x = min(x, y); }
void Max(int& x, int y) { x = max(x, y); }
int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 3) + (x << 1) + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
int n, q, rt;
struct Fhqtreap {
  long long ans[NR], ansl[NR], ansr[NR];
  int l[NR], r[NR], val[NR], siz[NR], key[NR], son[NR][2], tot;
  void update(int rt) {
    siz[rt] = siz[son[rt][0]] + siz[son[rt][1]] + 1;
    ans[rt] = ans[son[rt][0]] + ans[son[rt][1]];
    if (son[rt][0])
      ans[rt] += 1ll * siz[son[rt][0]] * (siz[son[rt][1]] + 1) *
                 (val[rt] - r[son[rt][0]]);
    if (son[rt][1])
      ans[rt] += 1ll * siz[son[rt][1]] * (siz[son[rt][0]] + 1) *
                 (l[son[rt][1]] - val[rt]);
    ans[rt] += 1ll * ansl[son[rt][0]] * (siz[son[rt][1]] + 1) +
               1ll * (siz[son[rt][0]] + 1) * ansr[son[rt][1]];
    ansl[rt] =
        ansl[son[rt][0]] +
        1ll * siz[son[rt][0]] * (val[rt] - r[son[rt][0]]) * (son[rt][0] != 0) +
        ansl[son[rt][1]];
    ansl[rt] += 1ll * (siz[son[rt][0]] + 1) * (l[son[rt][1]] - val[rt]) *
                    (son[rt][1] != 0) +
                1ll * (r[son[rt][1]] - l[son[rt][1]]) * (siz[son[rt][0]] + 1);
    ansr[rt] =
        ansr[son[rt][1]] +
        1ll * siz[son[rt][1]] * (l[son[rt][1]] - val[rt]) * (son[rt][1] != 0) +
        ansr[son[rt][0]];
    ansr[rt] += 1ll * (siz[son[rt][1]] + 1) * (val[rt] - r[son[rt][0]]) *
                    (son[rt][0] != 0) +
                1ll * (r[son[rt][0]] - l[son[rt][0]]) * (siz[son[rt][1]] + 1);
    l[rt] = r[rt] = val[rt];
    if (son[rt][1]) Max(r[rt], r[son[rt][1]]);
    if (son[rt][0]) Min(l[rt], l[son[rt][0]]);
  }
  void split(int rt, int k, int& x, int& y) {
    if (!rt) {
      x = y = 0;
      return;
    }
    if (val[rt] <= k)
      x = rt, split(son[rt][1], k, son[rt][1], y);
    else
      y = rt, split(son[rt][0], k, x, son[rt][0]);
    update(rt);
  }
  int merge(int x, int y) {
    if (!x || !y) return x | y;
    if (key[x] < key[y]) {
      son[x][1] = merge(son[x][1], y);
      update(x);
      return x;
    } else {
      son[y][0] = merge(x, son[y][0]);
      update(y);
      return y;
    }
  }
  int newnode(int x) {
    tot++;
    l[tot] = r[tot] = val[tot] = x;
    ans[tot] = 0, key[tot] = rand(), siz[tot] = 1;
    return tot;
  }
  void ins(int k) {
    int x, y;
    split(rt, k, x, y);
    rt = merge(merge(x, newnode(k)), y);
  }
  void del(int k) {
    int x, y, z;
    split(rt, k - 1, x, y);
    split(y, k, y, z);
    rt = merge(x, z);
  }
  long long query(int l, int r) {
    int x, y, z;
    split(rt, l - 1, x, y);
    split(y, r, y, z);
    long long res = ans[y];
    rt = merge(merge(x, y), z);
    return res;
  }
} T;
int a[NR];
int main() {
  n = read();
  for (int i = 1; i <= n; i++) a[i] = read(), T.ins(a[i]);
  q = read();
  for (int i = 1; i <= q; i++) {
    int op = read();
    if (op == 1) {
      int p = read(), d = read();
      T.del(a[p]), T.ins(a[p] + d);
      a[p] += d;
    } else {
      int l = read(), r = read();
      printf("%lld\n", T.query(l, r));
    }
  }
  return 0;
}
