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 MX = 1255555;
int alln, n, m, i, j, N, q[MX][5], x[MX], all[MX];
struct rec {
  long long cnt, sl, sr, s;
} a[MX];
bool u[MX];
void recount(int i, int L, int R, int h) {
  a[i].cnt = a[i * 2].cnt + a[i * 2 + 1].cnt;
  a[i].sl =
      a[i * 2].sl + a[i * 2 + 1].sl + a[i * 2 + 1].cnt * (all[h + 1] - all[L]);
  a[i].sr = a[i * 2].sr + a[i * 2 + 1].sr + a[i * 2].cnt * (all[R] - all[h]);
  a[i].s = a[i * 2].s + a[i * 2 + 1].s;
  a[i].s += a[i * 2].cnt *
            (a[i * 2 + 1].cnt * (all[h + 1] - all[h]) + a[i * 2 + 1].sl);
  a[i].s += a[i * 2 + 1].cnt * a[i * 2].sr;
}
void init(int i, int L, int R) {
  if (L == R) {
    a[i].cnt = int(u[L]);
    a[i].sl = a[i].sr = a[i].s = 0;
    return;
  }
  int h = (L + R) / 2;
  init(i * 2, L, h);
  init(i * 2 + 1, h + 1, R);
  recount(i, L, R, h);
}
void modify(int i, int L, int R, int x) {
  if (L == R) {
    a[i].cnt = int(u[L]);
    a[i].sl = a[i].sr = a[i].s = 0;
    return;
  }
  int h = (L + R) / 2;
  if (x <= h)
    modify(i * 2, L, h, x);
  else
    modify(i * 2 + 1, h + 1, R, x);
  recount(i, L, R, h);
}
rec count(int i, int L, int R, int l, int r) {
  rec cur;
  cur.cnt = 0;
  cur.sl = 0;
  cur.sr = 0;
  cur.s = 0;
  if (l > r) return cur;
  if (L == l && R == r) return a[i];
  int h = (L + R) / 2;
  if (l <= h && r > h) {
    rec cur1 = count(i * 2, L, h, l, h);
    rec cur2 = count(i * 2 + 1, h + 1, R, h + 1, r);
    cur.cnt = cur1.cnt + cur2.cnt;
    cur.sl = cur1.sl + cur2.sl + cur2.cnt * (all[h + 1] - all[L]);
    cur.sr = cur1.sr + cur2.sr + cur1.cnt * (all[R] - all[h]);
    cur.s = cur1.s + cur2.s;
    cur.s += cur1.cnt * (cur2.cnt * (all[h + 1] - all[h]) + cur2.sl);
    cur.s += cur2.cnt * cur1.sr;
  } else if (l > h) {
    return count(i * 2 + 1, h + 1, R, l, r);
  } else {
    return count(i * 2, L, h, l, r);
  }
  return cur;
}
int main() {
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d", &x[i]);
    all[i] = x[i];
  }
  alln = n;
  scanf("%d", &m);
  for (i = 0; i < m; i++) {
    for (j = 0; j < 3; j++) scanf("%d", &q[i][j]);
    if (q[i][0] == 1) {
      x[--q[i][1]] += q[i][2];
      all[alln++] = x[q[i][1]];
    }
  }
  for (i = 0; i < n; i++) x[i] = all[i];
  sort(all, all + alln);
  for (i = 0; i < n; i++) u[lower_bound(all, all + alln, x[i]) - all] = true;
  for (N = 1; N < alln; N *= 2)
    ;
  init(1, 0, N - 1);
  for (i = 0; i < m; i++)
    if (q[i][0] == 1) {
      int xx = lower_bound(all, all + alln, x[q[i][1]]) - all;
      u[xx] = false;
      modify(1, 0, N - 1, xx);
      x[q[i][1]] += q[i][2];
      xx = lower_bound(all, all + alln, x[q[i][1]]) - all;
      u[xx] = true;
      modify(1, 0, N - 1, xx);
    } else
      printf("%I64d\n",
             count(1, 0, N - 1, lower_bound(all, all + alln, q[i][1]) - all,
                   upper_bound(all, all + alln, q[i][2]) - all - 1)
                 .s);
  return 0;
}
