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;
int x[100005], cx[100005], disc[500005], ad[500005];
struct qu {
  int op, a, b;
} qq[100005];
struct tree {
  long long sum, ans, num;
};
tree tr[500005 << 2];
int num;
int get(int key) {
  int l = 1, r = num, mid;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (ad[mid] == key)
      return mid;
    else if (ad[mid] < key)
      l = mid + 1;
    else
      r = mid - 1;
  }
}
void pushup(int rt) {
  tr[rt].num = tr[rt << 1].num + tr[rt << 1 | 1].num;
  tr[rt].sum = tr[rt << 1].sum + tr[rt << 1 | 1].sum;
  tr[rt].ans = tr[rt << 1].ans + tr[rt << 1 | 1].ans +
               tr[rt << 1 | 1].sum * tr[rt << 1].num -
               tr[rt << 1].sum * tr[rt << 1 | 1].num;
}
void build(int l, int r, int rt) {
  tr[rt].ans = tr[rt].sum = tr[rt].num = 0;
  if (l == r) {
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
}
void modify(int pos, int val, int l, int r, int rt) {
  if (pos == l && pos == r) {
    if (val == 1) {
      tr[rt].sum = ad[pos];
      tr[rt].num++;
      tr[rt].ans = 0;
    } else {
      tr[rt].sum = tr[rt].ans = 0;
      tr[rt].num--;
    }
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    modify(pos, val, l, mid, rt << 1);
  else
    modify(pos, val, mid + 1, r, rt << 1 | 1);
  pushup(rt);
}
tree query(int ql, int qr, int l, int r, int rt) {
  if (ql == l && qr == r) {
    return tr[rt];
  }
  int mid = (l + r) >> 1;
  if (ql > mid)
    return query(ql, qr, mid + 1, r, rt << 1 | 1);
  else if (qr <= mid)
    return query(ql, qr, l, mid, rt << 1);
  else {
    tree tmp, t1 = query(ql, mid, l, mid, rt << 1),
              t2 = query(mid + 1, qr, mid + 1, r, rt << 1 | 1);
    tmp.num = t1.num + t2.num;
    tmp.sum = t1.sum + t2.sum;
    tmp.ans = t1.ans + t2.ans + t2.sum * t1.num - t1.sum * t2.num;
    return tmp;
  }
}
int main() {
  int n, i, m, cnt, pos, pos1;
  while (scanf("%d", &n) != EOF) {
    cnt = 0;
    for (i = 1; i <= n; i++) {
      scanf("%d", &x[i]);
      cx[i] = x[i];
      disc[cnt++] = x[i];
    }
    scanf("%d", &m);
    for (i = 1; i <= m; i++) {
      scanf("%d %d %d", &qq[i].op, &qq[i].a, &qq[i].b);
      if (qq[i].op == 1) {
        cx[qq[i].a] += qq[i].b;
        disc[cnt++] = cx[qq[i].a];
      } else {
        disc[cnt++] = qq[i].a;
        disc[cnt++] = qq[i].b;
      }
    }
    sort(disc, disc + cnt);
    ad[1] = disc[0];
    num = 1;
    for (i = 1; i < cnt; i++)
      if (disc[i] != disc[i - 1]) ad[++num] = disc[i];
    build(1, num, 1);
    for (i = 1; i <= n; i++) {
      pos = get(x[i]);
      modify(pos, 1, 1, num, 1);
    }
    for (i = 1; i <= m; i++) {
      if (qq[i].op == 1) {
        pos = get(x[qq[i].a]);
        modify(pos, -1, 1, num, 1);
        x[qq[i].a] += qq[i].b;
        pos = get(x[qq[i].a]);
        modify(pos, 1, 1, num, 1);
      } else {
        pos = get(qq[i].a);
        pos1 = get(qq[i].b);
        tree tmp = query(pos, pos1, 1, num, 1);
        printf("%I64d\n", tmp.ans);
      }
    }
  }
  return 0;
}
