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>
int pre[100111], nxt[100111][2], sz[100111], rt;
long long cnt[100111], sum[100111];
int num[100111], map[100111], rmap[100111];
std::set<int> set;
std::set<int>::const_iterator it;
inline void up(int id) {
  sz[id] = 1;
  cnt[id] = 0;
  sum[id] = num[map[id]];
  if (nxt[id][0]) {
    cnt[id] =
        cnt[nxt[id][0]] + (sum[id] * sz[nxt[id][0]] - sum[nxt[id][0]] * sz[id]);
    sz[id] += sz[nxt[id][0]];
    sum[id] += sum[nxt[id][0]];
  }
  if (nxt[id][1]) {
    cnt[id] +=
        cnt[nxt[id][1]] + (sum[nxt[id][1]] * sz[id] - sum[id] * sz[nxt[id][1]]);
    sz[id] += sz[nxt[id][1]];
    sum[id] += sum[nxt[id][1]];
  }
}
inline void rot(int id, int tp) {
  static int k;
  k = pre[id];
  nxt[k][tp ^ 1] = nxt[id][tp];
  if (nxt[id][tp]) pre[nxt[id][tp]] = k;
  if (pre[k]) nxt[pre[k]][k == nxt[pre[k]][1]] = id;
  pre[id] = pre[k];
  nxt[id][tp] = k;
  pre[k] = id;
  up(k);
  up(id);
}
inline void splay(int id, int to = 0) {
  while (pre[id] != to) rot(id, id == nxt[pre[id]][0]);
  if (!to) rt = id;
}
void make(int &id, int l, int r, int fa) {
  if (l <= r) {
    int mid((l + r) >> 1);
    id = mid;
    pre[id] = fa;
    make(nxt[id][0], l, mid - 1, id);
    make(nxt[id][1], mid + 1, r, id);
    up(id);
  }
}
inline int sel(int id, int k) {
  while (sz[nxt[id][0]] + 1 != k)
    if (sz[nxt[id][0]] >= k)
      id = nxt[id][0];
    else {
      k -= sz[nxt[id][0]] + 1;
      id = nxt[id][1];
    }
  return id;
}
inline int lb(int id, int val) {
  while (true)
    if (num[map[id]] > val) {
      if (!nxt[id][0]) return id;
      id = nxt[id][0];
    } else {
      if (!nxt[id][1]) return id;
      id = nxt[id][1];
    }
}
inline int find(int id, int val) {
  while (num[map[id]] != val)
    if (num[map[id]] < val)
      id = nxt[id][1];
    else
      id = nxt[id][0];
  return id;
}
void print(int id) {
  if (id) {
    print(nxt[id][0]);
    print(nxt[id][1]);
  }
}
int n, i, j, k, q, a, b, c;
int main() {
  scanf("%d", &n);
  for (i = 1; i <= n; ++i) {
    scanf("%d", num + i);
    set.insert(num[i]);
    map[i] = i;
  }
  std::sort(map + 1, map + 1 + n, [](int a, int b) { return num[a] < num[b]; });
  for (i = 1; i <= n; ++i) rmap[map[i]] = i;
  rt = ++n;
  num[n] = -0x3f3f3f3f;
  map[n] = rmap[n] = n;
  nxt[n][1] = n + 1;
  ++n;
  pre[n] = n - 1;
  num[n] = 0x3f3f3f3f;
  map[n] = rmap[n] = n;
  make(nxt[n][0], 1, n - 2, n);
  up(rt);
  set.insert(-0x3f3f3f3f);
  set.insert(0x3f3f3f3f);
  scanf("%d", &q);
  while (q--) {
    scanf("%d %d %d", &k, &i, &j);
    if (k == 1) {
      set.erase(num[i]);
      splay(rmap[i]);
      a = sz[nxt[rt][0]] + 1;
      splay(sel(rt, a - 1));
      splay(b = sel(rt, a + 1), rt);
      nxt[b][0] = 0;
      up(b);
      up(rt);
      num[i] += j;
      b = lb(rt, num[i]);
      c = (num[i] > num[map[b]]);
      nxt[b][c] = rmap[i];
      pre[rmap[i]] = b;
      splay(rmap[i]);
      set.insert(num[i]);
    } else {
      it = set.lower_bound(i);
      a = find(rt, *--it);
      it = set.upper_bound(j);
      b = find(rt, *it);
      splay(a);
      splay(b, a);
      printf("%I64d\n", cnt[nxt[b][0]]);
    }
  }
  return 0;
}
