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 oo = 1073741819;
struct seg {
  int cnt;
  long long sum, tot;
} S[1048576];
long long ans;
int n, m, m1, tot;
int a[1000000], b[1000000], c[1000000], u[1000000], oi[1000000],
    ask[1000000][3];
void origin() {
  for (m1 = 1; m1 <= tot + 2; m1 <<= 1)
    ;
}
void updata(seg &a, seg l, seg r) {
  a.sum = l.sum + r.sum + r.tot * l.cnt - l.tot * r.cnt;
  a.cnt = l.cnt + r.cnt;
  a.tot = l.tot + r.tot;
}
void change(int x, int c, long long w) {
  x += m1;
  S[x].cnt += c, S[x].tot += w;
  for (x >>= 1; x; x >>= 1) updata(S[x], S[x << 1], S[(x << 1) + 1]);
}
long long askl(int l, int r) {
  l += m1 - 1, r += m1 + 1;
  seg ans[2];
  memset(ans, 0, sizeof(ans));
  for (; !((l ^ r) == 1); l >>= 1, r >>= 1) {
    if ((l & 1) == 0) updata(ans[0], ans[0], S[l ^ 1]);
    if ((r & 1) == 1) updata(ans[1], S[r ^ 1], ans[1]);
  }
  updata(ans[0], ans[0], ans[1]);
  return ans[0].sum;
}
bool cmp(int i, int j) { return b[i] < b[j]; }
int main() {
  cin >> n;
  tot = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    b[++tot] = a[i], c[tot] = i;
  }
  cin >> m;
  for (int i = 1; i <= m; i++) {
    cin >> ask[i][0] >> ask[i][1] >> ask[i][2];
    if (ask[i][0] == 1) {
      b[++tot] = a[ask[i][1]], c[tot] = i + n;
      a[ask[i][1]] += ask[i][2];
      b[++tot] = a[ask[i][1]], c[tot] = i + n + m;
    } else {
      b[++tot] = ask[i][1], c[tot] = i + n;
      b[++tot] = ask[i][2], c[tot] = i + n + m;
    }
  }
  for (int i = 1; i <= tot; i++) u[i] = i;
  origin();
  sort(u + 1, u + tot + 1, cmp);
  b[u[0] = 0] = -oo;
  for (int i = 1, p = 0; i <= tot; i++) {
    if (b[u[i]] != b[u[i - 1]]) ++p;
    oi[p] = b[u[i]];
    if (c[u[i]] <= n)
      a[c[u[i]]] = p;
    else if (c[u[i]] <= n + m)
      ask[c[u[i]] - n][1] = p;
    else
      ask[c[u[i]] - n - m][2] = p;
  }
  for (int i = 1; i <= n; i++) change(a[i], 1, oi[a[i]]);
  for (int i = 1; i <= m; i++) {
    if (ask[i][0] == 1) {
      change(ask[i][1], -1, -oi[ask[i][1]]);
      change(ask[i][2], 1, oi[ask[i][2]]);
    } else {
      ans = askl(ask[i][1], ask[i][2]);
      cout << ans << endl;
    }
  }
  return 0;
}
