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 mod = 1e9 + 7;
struct node {
  long long inside, sum, size;
};
node add(node l, node r) {
  return {l.inside + r.inside - l.sum * r.size + r.sum * l.size, l.sum + r.sum,
          l.size + r.size};
}
struct seg {
  node tree[530000];
  void add(int pos, int real, int s, int e, int p, int v) {
    if (s == e) {
      if (v == -1)
        tree[p] = {0, 0, 0};
      else
        tree[p] = {0, real, 1};
      return;
    }
    int m = (s + e) / 2;
    if (pos <= m)
      add(pos, real, s, m, 2 * p, v);
    else
      add(pos, real, m + 1, e, 2 * p + 1, v);
    tree[p] = ::add(tree[2 * p], tree[2 * p + 1]);
  }
  node query(int s, int e, int ps, int pe, int p) {
    if (e < ps || pe < s) return {0, 0, 0};
    if (s <= ps && pe <= e) return tree[p];
    int pm = (ps + pe) / 2;
    return ::add(query(s, e, ps, pm, 2 * p),
                 query(s, e, pm + 1, pe, 2 * p + 1));
  }
} seg;
int n, q, a[100005], b[100005];
int t[100005], l[100005], r[100005];
vector<int> v;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    v.push_back(a[i]);
    b[i] = a[i];
  }
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d %d %d", &t[i], &l[i], &r[i]);
    if (t[i] == 1) {
      b[l[i]] += r[i];
      v.push_back(b[l[i]]);
    }
  }
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  int sz = v.size();
  for (int i = 1; i <= n; i++) {
    int lbnd = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
    seg.add(lbnd, a[i], 0, sz - 1, 1, 1);
  }
  for (int i = 0; i < q; i++) {
    if (t[i] == 1) {
      int lbnd = lower_bound(v.begin(), v.end(), a[l[i]]) - v.begin();
      seg.add(lbnd, a[l[i]], 0, sz - 1, 1, -1);
      a[l[i]] += r[i];
      lbnd = lower_bound(v.begin(), v.end(), a[l[i]]) - v.begin();
      seg.add(lbnd, a[l[i]], 0, sz - 1, 1, 1);
    } else {
      int lbnd = lower_bound(v.begin(), v.end(), l[i]) - v.begin();
      int ubnd = upper_bound(v.begin(), v.end(), r[i]) - v.begin() - 1;
      printf("%lld\n", seg.query(lbnd, ubnd, 0, sz - 1, 1).inside);
    }
  }
}
