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 MAXINT = 1001 * 1001 * 1001;
const int MAXN = 100001;
struct state {
  state *l, *r;
  state() { clear(); }
  void clear() {
    l = r = NULL;
    lsum = rsum = ans = count = 0;
  }
  long long lsum, rsum, ans, count;
};
int n, m;
int a[MAXN + 1];
state root;
void tree_addelem(state *v, int l, int r, int x) {
  if (l == r) {
    v->count = 1;
    return;
  }
  if (v->l == NULL) v->l = new state;
  if (v->r == NULL) v->r = new state;
  int lr = (l + r) >> 1;
  if (x <= lr)
    tree_addelem(v->l, l, lr, x);
  else
    tree_addelem(v->r, lr + 1, r, x);
  v->count = v->l->count + v->r->count;
  v->lsum = v->l->lsum + v->r->lsum + v->r->count * (lr - l + 1);
  v->rsum = v->r->rsum + v->l->rsum + v->l->count * (r - (lr + 1) + 1);
  v->ans = v->l->ans + v->r->ans + v->l->rsum * v->r->count +
           v->r->lsum * v->l->count + v->r->count * v->l->count;
}
void tree_delete(state *v, int l, int r, int x) {
  if (l == r) {
    v->clear();
    return;
  }
  int lr = (l + r) >> 1;
  if (x <= lr)
    tree_delete(v->l, l, lr, x);
  else
    tree_delete(v->r, lr + 1, r, x);
  if (v->l->count == 0 && v->r->count == 0) {
    delete (v->l);
    delete (v->r);
    v->clear();
    return;
  }
  v->count = v->l->count + v->r->count;
  v->lsum = v->l->lsum + v->r->lsum + v->r->count * (lr - l + 1);
  v->rsum = v->r->rsum + v->l->rsum + v->l->count * (r - (lr + 1) + 1);
  v->ans = v->l->ans + v->r->ans + v->l->rsum * v->r->count +
           v->r->lsum * v->l->count + v->r->count * v->l->count;
}
state tree_get(state *v, int l, int r, int pl, int pr) {
  if (pl > pr) {
    state res;
    return res;
  }
  if (l == pl && r == pr) return *v;
  int lr = (l + r) >> 1;
  state sl, sr;
  if (v->l != NULL) sl = tree_get(v->l, l, lr, pl, min(lr, pr));
  if (v->r != NULL) sr = tree_get(v->r, lr + 1, r, max(lr + 1, pl), pr);
  state res;
  res.count = sl.count + sr.count;
  res.lsum = sl.lsum + sr.lsum + sr.count * (lr - l + 1);
  res.rsum = sr.rsum + sl.rsum + sl.count * (r - (lr + 1) + 1);
  res.ans = sl.ans + sr.ans + sl.rsum * sr.count + sr.lsum * sl.count +
            sr.count * sl.count;
  return res;
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
    tree_addelem(&root, -MAXINT, MAXINT, a[i]);
  }
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    int t;
    scanf("%d", &t);
    switch (t) {
      case 1:
        int p, d;
        scanf("%d%d", &p, &d);
        tree_delete(&root, -MAXINT, MAXINT, a[p - 1]);
        a[p - 1] += d;
        tree_addelem(&root, -MAXINT, MAXINT, a[p - 1]);
        break;
      case 2:
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%I64d\n", tree_get(&root, -MAXINT, MAXINT, l, r).ans);
        break;
    }
  }
  return 0;
}
