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 INF = 2147483647;
const long long LLINF = 9223372036854775807LL;
struct node {
  int l, r;
  long long x;
  int y;
  int subsize;
  long long subsum;
  long long sum2;
  node() : l(0), r(0), x(0), y(0), subsize(0), subsum(0), sum2(0) {}
};
const int maxn = 100010;
int mem = 1;
node t[maxn];
void recalc(int v) {
  if (v == 0) return;
  t[v].subsize = t[t[v].l].subsize + t[t[v].r].subsize + 1;
  t[v].subsum = t[t[v].l].subsum + t[t[v].r].subsum + t[v].x;
  t[v].sum2 = t[t[v].l].sum2 + t[v].x * t[t[v].l].subsize + t[t[v].r].sum2 +
              t[t[v].r].subsum * (t[t[v].l].subsize + 1);
}
void split(int v, int k, int& tl, int& tr) {
  if (v == 0) {
    tl = tr = 0;
    return;
  }
  if (t[v].x <= k) {
    split(t[v].r, k, t[v].r, tr);
    recalc(v);
    tl = v;
  } else {
    split(t[v].l, k, tl, t[v].l);
    recalc(v);
    tr = v;
  }
}
int merge(int tl, int tr) {
  if (tl == 0) return tr;
  if (tr == 0) return tl;
  if (t[tl].y > t[tr].y) {
    t[tl].r = merge(t[tl].r, tr);
    recalc(tl);
    return tl;
  } else {
    t[tr].l = merge(tl, t[tr].l);
    recalc(tr);
    return tr;
  }
}
int getnode(long long x) {
  t[mem].x = x;
  t[mem].y = rand() | (rand() << 15);
  t[mem].subsize = 1;
  t[mem].subsum = x;
  t[mem].sum2 = 0;
  return mem++;
}
int ind[maxn];
int main() {
  int root = 0;
  int n;
  scanf("%d", &n);
  vector<pair<int, int> > v(n);
  for (int i = 0; i < n; ++i) scanf("%d", &v[i].first), v[i].second = i;
  sort(v.begin(), v.end());
  for (int i = 0; i < n; ++i) {
    int curind = getnode(v[i].first);
    ind[v[i].second] = curind;
    root = merge(root, curind);
  }
  int m;
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    int ti;
    scanf("%d", &ti);
    if (ti == 1) {
      int pj, dj;
      scanf("%d%d", &pj, &dj);
      --pj;
      int curx = t[ind[pj]].x;
      int tox = curx + dj;
      int tl, tm, tr;
      split(root, curx, tl, tr);
      split(tl, curx - 1, tl, tm);
      root = merge(tl, tr);
      int tmp = tm;
      assert(t[tmp].subsize == 1);
      t[tmp].x += dj;
      t[tmp].subsum += dj;
      split(root, tox, tl, tr);
      split(tl, tox - 1, tl, tm);
      assert(tm == 0);
      root = merge(tl, merge(tmp, tr));
    } else {
      int li, ri;
      scanf("%d%d", &li, &ri);
      int tl, tm, tr;
      split(root, ri, tl, tr);
      split(tl, li - 1, tl, tm);
      long long ans = 2LL * t[tm].sum2 - t[tm].subsum * (t[tm].subsize - 1);
      printf("%I64d\n", ans);
      root = merge(tl, merge(tm, tr));
    }
  }
  return 0;
}
