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;
struct vert {
  long long sumx, sumdiff;
  int qua;
  int x;
  int ord;
  vert *lt, *rt;
  vert(int _x) : x(_x) {
    sumdiff = 0;
    sumx = x;
    qua = 1;
    ord = rand();
    lt = rt = 0;
  }
};
void norm(vert* r) {
  if (r == 0) return;
  r->qua = 1;
  r->sumx = r->x;
  r->sumdiff = 0;
  long long ql = 0, qr = 0, qlsx = 0, qrsx = 0;
  if (r->lt != 0) {
    r->qua += r->lt->qua;
    r->sumdiff += r->lt->sumdiff;
    r->sumx += r->lt->sumx;
    ql = r->lt->qua;
    qlsx = r->lt->sumx;
  }
  if (r->rt != 0) {
    r->qua += r->rt->qua;
    r->sumdiff += r->rt->sumdiff;
    r->sumx += r->rt->sumx;
    qr = r->rt->qua;
    qrsx = r->rt->sumx;
  }
  r->sumdiff += ql * qrsx - qr * qlsx + ql * r->x - qlsx + qrsx - qr * r->x;
}
vert* merge(vert* a, vert* b) {
  if (a == 0) return b;
  if (b == 0) return a;
  if (a->ord > b->ord) {
    a->rt = merge(a->rt, b);
    norm(a);
    return a;
  } else {
    b->lt = merge(a, b->lt);
    norm(b);
    return b;
  }
}
void split(vert* root, int key, vert*& ansl, vert*& ansr) {
  if (root == 0) {
    ansr = ansl = 0;
    return;
  }
  if (root->x <= key) {
    split(root->rt, key, root->rt, ansr);
    norm(root);
    ansl = root;
  } else {
    split(root->lt, key, ansl, root->lt);
    norm(root);
    ansr = root;
  }
}
int x[100000];
void insert(vert*& r, int k) {
  vert *lt, *rt;
  split(r, k, lt, rt);
  r = merge(lt, merge(new vert(k), rt));
}
void remove(vert*& r, int k) {
  vert *lt, *mt, *rt;
  split(r, k, mt, rt);
  split(mt, k - 1, lt, mt);
  r = merge(lt, rt);
  delete mt;
}
long long query(vert*& root, int l, int r) {
  vert *lt, *mt, *rt;
  split(root, r, mt, rt);
  split(mt, l - 1, lt, mt);
  long long ans = 0;
  if (mt != 0) {
    ans = mt->sumdiff;
  }
  root = merge(merge(lt, mt), rt);
  return ans;
}
int n;
int ssx[100000];
vert* mtree = 0;
void check(int& l, vert* root) {
  if (root == 0) return;
  check(l, root->lt);
  assert(ssx[l] == root->x);
  check(++l, root->rt);
  vert old = *root;
  norm(root);
  assert(old.qua == root->qua);
  assert(old.sumx == root->sumx);
  assert(old.sumdiff == root->sumdiff);
}
void assrt() {
  for (int i = 0; i < n; i++) ssx[i] = x[i];
  sort(ssx, ssx + n);
  int c = 0;
  check(c, mtree);
}
int main() {
  ios_base::sync_with_stdio(false);
  int m;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> x[i];
    insert(mtree, x[i]);
  }
  cin >> m;
  for (int i = 0; i < m; i++) {
    int t;
    cin >> t;
    if (t == 1) {
      int p, d;
      cin >> p >> d;
      p--;
      remove(mtree, x[p]);
      x[p] += d;
      insert(mtree, x[p]);
    } else {
      int l, r;
      cin >> l >> r;
      cout << query(mtree, l, r) << "\n";
    }
  }
}
