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;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
int rng(int l, int r) { return uniform_int_distribution<int>(l, r)(gen); }
struct Treap;
using twoTreaps = array<Treap *, 2>;
struct Treap {
  int val;
  long long sum;
  long long res;
  int sz;
  int priority;
  twoTreaps kids;
  Treap(int a) {
    val = a;
    sum = a;
    res = 0;
    sz = 1;
    priority = rng(1, (1 << 30));
    kids[0] = kids[1] = nullptr;
  }
};
int sz(Treap *me) { return (me ? me->sz : 0); }
void recalc(Treap *me) {
  if (!me) return;
  me->sz = 1;
  for (Treap *to : me->kids)
    if (to) me->sz += to->sz;
  me->sum = me->val;
  for (Treap *to : me->kids)
    if (to) me->sum += to->sum;
  me->res = 0;
  for (Treap *to : me->kids)
    if (to) me->res += to->res;
  if (me->kids[0])
    me->res += ((long long)sz(me->kids[0]) * me->val - me->kids[0]->sum);
  if (me->kids[1])
    me->res += (me->kids[1]->sum - (long long)sz(me->kids[1]) * me->val);
  if (me->kids[0] && me->kids[1])
    me->res += ((long long)sz(me->kids[0]) * me->kids[1]->sum -
                (long long)sz(me->kids[1]) * me->kids[0]->sum);
}
twoTreaps splitval(Treap *me, int lim) {
  if (!me) return {nullptr, nullptr};
  if (me->val > lim) {
    twoTreaps res = splitval(me->kids[0], lim);
    me->kids[0] = res[1];
    recalc(me);
    return {res[0], me};
  } else {
    twoTreaps res = splitval(me->kids[1], lim);
    me->kids[1] = res[0];
    recalc(me);
    return {me, res[1]};
  }
}
Treap *tmerge(Treap *a, Treap *b) {
  if (!a) return b;
  if (!b) return a;
  if (a->priority < b->priority) {
    a->kids[1] = tmerge(a->kids[1], b);
    recalc(a);
    return a;
  } else {
    b->kids[0] = tmerge(a, b->kids[0]);
    recalc(b);
    return b;
  }
}
Treap *tinsert(Treap *me, Treap *a) {
  twoTreaps res = splitval(me, a->val);
  return tmerge(tmerge(res[0], a), res[1]);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> x(n + 1, 0);
  for (int i = 1; i <= n; i++) cin >> x[i];
  Treap *root = new Treap(x[1]);
  for (int i = 2; i <= n; i++) root = tinsert(root, new Treap(x[i]));
  int m;
  cin >> m;
  while (m--) {
    int t, l, r;
    cin >> t >> l >> r;
    if (t == 1) {
      auto [one, tmp] = splitval(root, x[l] - 1);
      auto [two, three] = splitval(tmp, x[l]);
      root = tmerge(one, three);
      x[l] += r;
      root = tinsert(root, new Treap(x[l]));
    } else if (t == 2) {
      auto [one, tmp] = splitval(root, l - 1);
      auto [two, three] = splitval(tmp, r);
      cout << (two ? two->res : 0) << "\n";
      root = tmerge(tmerge(one, two), three);
    }
  }
  return 0;
}
