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 MAX = int(1e5) + 10;
typedef struct node* pnode;
long long myrand() { return rand() << 16 + rand(); }
struct node {
  int value, cnt;
  long long prior, sum1, sum2;
  pnode l, r;
  node() {}
  node(int value, long long prior)
      : value(value),
        cnt(1),
        prior(prior),
        sum1(value),
        sum2(value),
        l(NULL),
        r(NULL) {}
};
int cnt(pnode it) { return it ? it->cnt : 0; }
void upd_cnt(pnode it) {
  if (it) it->cnt = cnt(it->l) + cnt(it->r) + 1;
}
void update_sum(pnode it) {
  if (it) {
    int cc = cnt(it->l) + 1;
    it->sum1 = it->value;
    it->sum2 = (long long)it->value * cc;
    if (it->l) {
      it->sum1 += it->l->sum1;
      it->sum2 += it->l->sum2;
    }
    if (it->r) {
      it->sum1 += it->r->sum1;
      it->sum2 += it->r->sum2 + cc * it->r->sum1;
    }
  }
}
void merge(pnode& t, pnode l, pnode r) {
  if (!l || !r)
    t = l ? l : r;
  else if (l->prior > r->prior)
    merge(l->r, l->r, r), t = l;
  else
    merge(r->l, l, r->l), t = r;
  upd_cnt(t);
  update_sum(t);
}
void lower_split(pnode t, pnode& l, pnode& r, int key) {
  if (!t) return void(l = r = 0);
  int cur_key = t->value;
  if (key <= cur_key)
    lower_split(t->l, l, t->l, key), r = t;
  else
    lower_split(t->r, t->r, r, key), l = t;
  upd_cnt(t);
  update_sum(t);
}
void upper_split(pnode t, pnode& l, pnode& r, int key) {
  if (!t) return void(l = r = 0);
  int cur_key = t->value;
  if (key < cur_key)
    upper_split(t->l, l, t->l, key), r = t;
  else
    upper_split(t->r, t->r, r, key), l = t;
  upd_cnt(t);
  update_sum(t);
}
void insert(pnode& t, int val) {
  pnode t1, t2, it;
  lower_split(t, t1, t2, val);
  it = new node(val, myrand());
  merge(t, t1, it);
  merge(t, t, t2);
}
void erase(pnode& t, int key) {
  if (!t) return;
  int cur_key = t->value;
  if (cur_key == key)
    merge(t, t->l, t->r);
  else if (key < cur_key)
    erase(t->l, key);
  else
    erase(t->r, key);
  upd_cnt(t);
  update_sum(t);
}
long long query(pnode t, int l, int r) {
  pnode t1, t2, t3;
  lower_split(t, t1, t2, l);
  upper_split(t2, t2, t3, r);
  long long ans = 0;
  if (t2) {
    ans = 2 * t2->sum2 - (t2->cnt + 1) * t2->sum1;
  }
  merge(t, t1, t2);
  merge(t, t, t3);
  return ans;
}
int N;
int a[MAX];
pnode root;
int main() {
  root = NULL;
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) {
    scanf("%d", a + i);
    insert(root, a[i]);
  }
  int Q;
  scanf("%d", &Q);
  while (Q--) {
    int typ, x, y;
    scanf("%d%d%d", &typ, &x, &y);
    if (typ == 1) {
      erase(root, a[x]);
      a[x] += y;
      insert(root, a[x]);
    } else {
      long long ans = query(root, x, y);
      printf("%I64d\n", ans);
    }
  }
  return 0;
}
