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;
template <class T>
inline T bigmod(T p, T e, T M) {
  if (e == 0) return 1;
  if (e % 2 == 0) {
    T t = bigmod(p, e / 2, M);
    return (t * t) % M;
  }
  return (bigmod(p, e - 1, M) * p) % M;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
struct node {
  int st, ed, cnt;
  long long ls, rs, sum;
  node *l, *r;
  node(long long s, long long e) {
    st = s;
    ed = e;
    ls = rs = 0;
    cnt = sum = 0;
    l = r = NULL;
  }
};
void insert(node *ob, int p, int v) {
  if (ob->st == ob->ed) {
    if (v == 1) {
      ob->cnt++;
      ob->ls = 1;
      ob->rs = 1;
    } else {
      ob->cnt--;
      ob->ls = 0;
      ob->rs = 0;
    }
    return;
  }
  int mid = ((long long)ob->st + (long long)ob->ed) / 2;
  if (ob->l == NULL) ob->l = new node(ob->st, mid);
  if (ob->r == NULL) ob->r = new node(mid + 1, ob->ed);
  if (p <= mid)
    insert(ob->l, p, v);
  else
    insert(ob->r, p, v);
  if (v == 1) {
    ob->ls += (long long)(p - ob->st + 1);
    ob->rs += (long long)(ob->ed - p + 1);
    ob->cnt++;
  } else {
    ob->ls -= (long long)(p - ob->st + 1);
    ob->rs -= (long long)(ob->ed - p + 1);
    ob->cnt--;
  }
  ob->sum =
      ob->l->sum + ob->r->sum + ob->l->cnt * ob->r->ls + ob->r->cnt * ob->l->rs;
}
long long nc;
long long sum;
long long query(node *ob, int s, int e) {
  if (ob->st == s && ob->ed == e) {
    long long ret = ob->cnt * sum + nc * ob->ls + ob->sum;
    sum += nc * (e - s + 1);
    nc += ob->cnt;
    sum += ob->rs;
    return ret;
  }
  int mid = ((long long)ob->st + (long long)ob->ed) / 2;
  if (ob->l == NULL) ob->l = new node(ob->st, mid);
  if (ob->r == NULL) ob->r = new node(mid + 1, ob->ed);
  if (e <= mid)
    return query(ob->l, s, e);
  else if (s > mid)
    return query(ob->r, s, e);
  return query(ob->l, s, mid) + query(ob->r, mid + 1, e);
}
long long ar[100001];
int main() {
  long long a, b, c, d, e, f, x, y, z;
  cin >> a;
  node *root = new node(0, 2000000000);
  for (x = 1; x <= a; x++) {
    cin >> b;
    b += 1000000000;
    insert(root, b, 1);
    ar[x] = b;
  }
  cin >> b;
  for (x = 0; x < b; x++) {
    cin >> c >> d >> e;
    if (c == 1) {
      insert(root, ar[d], 0);
      ar[d] += e;
      insert(root, ar[d], 1);
    } else {
      sum = 0;
      nc = 0;
      d += 1000000000;
      e += 1000000000;
      f = query(root, d, e);
      f -= nc * (nc - 1) / 2;
      cout << f << endl;
    }
  }
}
