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>
const long long oo = 1000000000LL;
using namespace std;
long long l[5000000], r[5000000], n, m, ans[2000000], ss;
long long sum[5000000], tot[5000000], L, R, mid, a[200000], cnt[5000000];
void ask(long long s, long long L, long long R, long long lx, long long rx) {
  if (!cnt[s]) return;
  if (L == lx && R == rx) {
    ans[++ans[0]] = s;
    return;
  }
  long long mid = (L + R) >> 1;
  if (lx <= mid) ask(l[s], L, mid, lx, min(rx, mid));
  if (rx > mid) ask(r[s], mid + 1, R, max(lx, mid + 1), rx);
}
void updata(long long s) {
  sum[s] =
      sum[l[s]] + sum[r[s]] + tot[r[s]] * cnt[l[s]] - tot[l[s]] * cnt[r[s]];
  cnt[s] = cnt[l[s]] + cnt[r[s]];
  tot[s] = tot[l[s]] + tot[r[s]];
}
long long del(long long s, long long x) {
  if (L == R) {
    sum[s] = 0, cnt[s]--, tot[s] -= L - oo;
    return L;
  }
  mid = (L + R) >> 1;
  ;
  if (x <= mid) {
    R = mid;
    long long sum = del(l[s], x);
    updata(s);
    return sum;
  } else {
    L = mid + 1;
    long long sum = del(r[s], x);
    updata(s);
    return sum;
  }
}
void add(long long s, long long x) {
  if (L == R) {
    sum[s] = 0, cnt[s]++, tot[s] += x - oo;
    return;
  }
  mid = (L + R) >> 1;
  if (x <= mid) {
    R = mid;
    if (!l[s]) l[s] = ++ss;
    add(l[s], x);
    updata(s);
  } else {
    L = mid + 1;
    if (!r[s]) r[s] = ++ss;
    add(r[s], x);
    updata(s);
  }
}
int main() {
  cin >> n;
  ss = 1;
  for (int i = 1; i <= n; i++) {
    long long x;
    cin >> x;
    x += oo;
    L = 0, R = oo + oo;
    add(1, x);
    a[i] = x;
  }
  cin >> m;
  for (int j = 1; j <= m; j++) {
    long long t;
    long long x, y, d;
    cin >> t;
    if (1 == t) {
      cin >> x >> d;
      L = 0, R = oo + oo;
      y = del(1, a[x]);
      L = 0, R = oo + oo;
      add(1, y + d);
      a[x] = y + d;
    } else {
      cin >> x >> y;
      x += oo, y += oo;
      L = 0, R = oo + oo;
      ans[0] = 0;
      ask(1, L, R, x, y);
      long long ansum = 0, ancnt = 0, antot = 0;
      for (long long i = 1; i <= ans[0]; i++) {
        long long s = ans[i];
        ansum += sum[s] + tot[s] * ancnt - antot * cnt[s];
        ancnt += cnt[s];
        antot += tot[s];
      }
      cout << ansum << endl;
    }
  }
  return 0;
}
