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 n, a[222222], tt, xx, yy, m, kk, u[222222];
pair<int, int> qq[222222];
struct node {
  int left, right;
  int xkor, lkor, rkor, pr;
  long long sum, sl, sr, kol;
} N[222222];
int make(int x) {
  kk++;
  N[kk].left = N[kk].right = 0;
  N[kk].xkor = N[kk].lkor = N[kk].rkor = x;
  N[kk].kol = 1;
  N[kk].pr = rand();
  N[kk].sum = N[kk].sl = N[kk].sr = 0;
  return kk;
}
void up(int x) {
  if (x == 0) return;
  N[x].lkor = N[x].rkor = N[x].xkor;
  N[x].sum = 0;
  N[x].kol = 1;
  if (N[x].left != 0) {
    N[x].lkor = N[N[x].left].lkor;
    N[x].kol += N[N[x].left].kol;
    N[x].sum += N[N[x].left].sum;
  }
  if (N[x].right != 0) {
    N[x].rkor = N[N[x].right].rkor;
    N[x].kol += N[N[x].right].kol;
    N[x].sum += N[N[x].right].sum;
  }
  N[x].sr = N[x].rkor - N[x].xkor;
  if (N[x].right != 0) N[x].sr += N[N[x].right].sr;
  if (N[x].left != 0)
    N[x].sr +=
        N[N[x].left].sr + N[N[x].left].kol * (N[x].rkor - N[N[x].left].rkor);
  N[x].sl = N[x].xkor - N[x].lkor;
  if (N[x].left != 0) N[x].sl += N[N[x].left].sl;
  if (N[x].right != 0)
    N[x].sl +=
        N[N[x].right].sl + N[N[x].right].kol * (N[N[x].right].lkor - N[x].lkor);
  if (N[x].left != 0) {
    N[x].sum +=
        N[N[x].left].sr + N[N[x].left].kol * (N[x].xkor - N[N[x].left].rkor);
  }
  if (N[x].right != 0) {
    N[x].sum +=
        N[N[x].right].sl + N[N[x].right].kol * (N[N[x].right].lkor - N[x].xkor);
  }
  if (N[x].left != 0 && N[x].right != 0) {
    N[x].sum += N[N[x].left].sr * N[N[x].right].kol;
    N[x].sum += N[N[x].right].sl * N[N[x].left].kol;
    N[x].sum += N[N[x].left].kol * N[N[x].right].kol *
                (N[N[x].right].lkor - N[N[x].left].rkor);
  }
}
int les(int t, int x) {
  if (t == 0) return 0;
  if (N[t].xkor < x) return N[N[t].left].kol + 1 + les(N[t].right, x);
  return les(N[t].left, x);
}
void cut(int t, int x, int &t1, int &t2) {
  t1 = t2 = 0;
  if (x == 0) {
    t2 = t;
    return;
  }
  if (x == N[t].kol) {
    t1 = t;
    return;
  }
  int q1, q2;
  if (N[N[t].left].kol >= x) {
    cut(N[t].left, x, q1, q2);
    t1 = q1;
    N[t].left = q2;
    t2 = t;
  } else {
    cut(N[t].right, x - N[N[t].left].kol - 1, q1, q2);
    t2 = q2;
    N[t].right = q1;
    t1 = t;
  }
  up(t);
}
int merge(int t1, int t2) {
  if (t2 == 0 && t1 == 0) return 0;
  if (t1 == 0) return t2;
  if (t2 == 0) return t1;
  if (N[t1].pr < N[t2].pr) {
    N[t1].right = merge(N[t1].right, t2);
    up(t1);
    return t1;
  } else {
    N[t2].left = merge(t1, N[t2].left);
    up(t2);
    return t2;
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]), qq[i] = make_pair(a[i], i);
  sort(qq, qq + n);
  sort(a, a + n);
  for (int i = 0; i < n; i++) u[qq[i].second] = i;
  int o = make(a[0]), t1, t2;
  for (int i = 1; i < n; i++) {
    int t = make(a[i]);
    o = merge(o, t);
  }
  cin >> m;
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d", &tt, &xx, &yy);
    if (tt == 1) {
      xx--;
      int h = les(o, a[u[xx]]);
      cut(o, h, t1, o);
      cut(o, 1, t2, o);
      o = merge(t1, o);
      a[u[xx]] += yy;
      N[t2].xkor += yy;
      N[t2].lkor = N[t2].rkor = N[t2].xkor;
      h = les(o, a[u[xx]]);
      cut(o, h, t1, o);
      o = merge(t2, o);
      o = merge(t1, o);
    } else {
      int h = les(o, yy + 1);
      cut(o, h, o, t2);
      h = les(o, xx);
      cut(o, h, t1, o);
      cout << N[o].sum << endl;
      o = merge(t1, o);
      o = merge(o, t2);
    }
  }
  return 0;
}
