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;
using ll = long long;
const int N = 100 * 1000 + 10, INF = 1e9 + 10;
ll n, m, a[N];
struct node {
  ll sm, ans;
  int cnt;
  node *lc, *rc;
  node() {
    lc = rc = NULL;
    sm = cnt = ans = 0;
  }
  void merge() {
    ans = lc->ans + rc->ans + rc->sm * lc->cnt - lc->sm * rc->cnt;
    sm = lc->sm + rc->sm;
    cnt = lc->cnt + rc->cnt;
  }
  void merge(node a, node b) {
    ans = a.ans + b.ans + b.sm * a.cnt - a.sm * b.cnt;
    sm = a.sm + b.sm;
    cnt = a.cnt + b.cnt;
  }
  void build_c() {
    if (lc != NULL) return;
    lc = new node();
    rc = new node();
  }
} segment;
void upd(int x, int k, node *seg = &segment, int l = -INF, int r = INF) {
  if (x < l || x >= r) return;
  if (r - l == 1)
    return seg->ans = 0, seg->cnt = k, seg->sm = (k ? l : 0), void();
  int mid = l + r >> 1;
  seg->build_c();
  upd(x, k, seg->lc, l, mid), upd(x, k, seg->rc, mid, r);
  seg->merge();
}
node get(int lq, int rq, node *seg = &segment, int l = -INF, int r = INF) {
  if (r <= lq || rq <= l) return node();
  if (lq <= l && r <= rq) return *seg;
  int mid = l + r >> 1;
  seg->build_c();
  node res;
  res.merge(get(lq, rq, seg->lc, l, mid), get(lq, rq, seg->rc, mid, r));
  return res;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i], upd(a[i], 1);
  cin >> m;
  int t, x, y;
  while (m--) {
    cin >> t >> x >> y, --t;
    if (t) {
      y++;
      cout << get(x, y).ans << '\n';
    } else {
      --x;
      upd(a[x], 0);
      a[x] += y;
      upd(a[x], 1);
    }
  }
}
