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 maxn = 400010;
struct node {
  int l, r;
  int num;
  long long s;
  long long sum;
} seg[4 * maxn];
int inv[maxn];
void pushup(int th) {
  seg[th].num = seg[2 * th].num + seg[2 * th + 1].num;
  seg[th].s = seg[2 * th].s + seg[2 * th + 1].s;
  seg[th].sum = seg[2 * th].sum + seg[2 * th + 1].sum;
  seg[th].sum +=
      seg[2 * th].num * seg[2 * th + 1].s - seg[2 * th + 1].num * seg[2 * th].s;
}
void build(int l, int r, int th) {
  seg[th].l = l;
  seg[th].r = r;
  seg[th].sum = seg[th].s = seg[th].num = 0;
  if (l != r) {
    int mid = (l + r) / 2;
    build(l, mid, 2 * th);
    build(mid + 1, r, 2 * th + 1);
  }
}
void update(int pos, int th, bool f) {
  if (seg[th].l == seg[th].r) {
    if (f) {
      seg[th].num = 1;
      seg[th].s = inv[pos];
      seg[th].sum = 0;
    } else {
      seg[th].num = seg[th].s = seg[th].sum = 0;
    }
  } else {
    int mid = (seg[th].l + seg[th].r) / 2;
    if (pos <= mid)
      update(pos, 2 * th, f);
    else
      update(pos, 2 * th + 1, f);
    pushup(th);
  }
}
node query(int l, int r, int th) {
  if (seg[th].l == l && seg[th].r == r) return seg[th];
  int mid = (seg[th].l + seg[th].r) / 2;
  if (r <= mid) return query(l, r, 2 * th);
  if (l > mid) return query(l, r, 2 * th + 1);
  node L = query(l, mid, 2 * th);
  node R = query(mid + 1, r, 2 * th + 1);
  node ans;
  ans.num = L.num + R.num;
  ans.s = L.s + R.s;
  ans.sum = L.sum + R.sum + R.s * L.num - L.s * R.num;
  return ans;
}
int n, a[maxn];
int m;
int type[maxn], L[maxn], R[maxn];
int A[maxn];
int gao[maxn];
map<int, int> mp;
int main() {
  while (~scanf("%d", &n)) {
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
      scanf("%d %d %d", &type[i], &L[i], &R[i]);
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) A[i] = a[i];
    for (int i = 1; i <= n; i++) gao[++cnt] = a[i];
    for (int i = 1; i <= m; i++)
      if (type[i] == 1) {
        A[L[i]] += R[i];
        gao[++cnt] = A[L[i]];
      } else {
        gao[++cnt] = L[i];
        gao[++cnt] = R[i];
      }
    sort(gao + 1, gao + 1 + cnt);
    mp.clear();
    int now = 0;
    for (int i = 1; i <= cnt; i++) {
      if (i == 1 || gao[i] != gao[i - 1]) mp[gao[i]] = ++now, inv[now] = gao[i];
    }
    build(1, now, 1);
    for (int i = 1; i <= n; i++) update(mp[a[i]], 1, 1);
    for (int i = 1; i <= m; i++) {
      if (type[i] == 1) {
        update(mp[a[L[i]]], 1, 0);
        a[L[i]] += R[i];
        update(mp[a[L[i]]], 1, 1);
      } else {
        printf("%I64d\n", query(mp[L[i]], mp[R[i]], 1).sum);
      }
    }
  }
}
