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;
struct Op {
  int kind;
  long long t1, t2;
} op[662255];
long long x[662255], a[662255];
long long num[662255], disl[662255], disr[662255], sum[662255];
long long _num[662255], _disl[662255], _disr[662255], _sum[662255];
bool f[662255];
void clean(int now) { _num[now] = _disl[now] = _disr[now] = _sum[now] = 0; }
void pushUp(int l, int r, int now) {
  int mid = (l + r) / 2;
  sum[now] = sum[now * 2] + sum[now * 2 + 1] +
             disr[now * 2] * num[now * 2 + 1] +
             disl[now * 2 + 1] * num[now * 2] +
             (a[mid + 1] - a[mid]) * (num[now * 2] * num[now * 2 + 1]);
  disl[now] = disl[now * 2] + disl[now * 2 + 1] +
              (a[mid + 1] - a[l]) * num[now * 2 + 1];
  disr[now] =
      disr[now * 2 + 1] + disr[now * 2] + (a[r] - a[mid]) * num[now * 2];
  num[now] = num[now * 2] + num[now * 2 + 1];
}
void _pushUp(int l, int r, int now) {
  int mid = (l + r) / 2;
  _sum[now] = _sum[now * 2] + _sum[now * 2 + 1] +
              _disr[now * 2] * _num[now * 2 + 1] +
              _disl[now * 2 + 1] * _num[now * 2] +
              (a[mid + 1] - a[mid]) * (_num[now * 2] * _num[now * 2 + 1]);
  _disl[now] = _disl[now * 2] + _disl[now * 2 + 1] +
               (a[mid + 1] - a[l]) * _num[now * 2 + 1];
  _disr[now] =
      _disr[now * 2 + 1] + _disr[now * 2] + (a[r] - a[mid]) * _num[now * 2];
  _num[now] = _num[now * 2] + _num[now * 2 + 1];
}
void buildtree(int l, int r, int now) {
  if (l == r) {
    if (f[l])
      num[now] = 1;
    else
      num[now] = 0;
    disl[now] = disr[now] = sum[now] = 0;
    return;
  }
  int mid = (l + r) / 2;
  buildtree(l, mid, now * 2);
  buildtree(mid + 1, r, now * 2 + 1);
  pushUp(l, r, now);
}
void update(int l, int r, int k, bool flag, int now) {
  if (l == r) {
    if (flag)
      num[now] = 1;
    else
      num[now] = 0;
    sum[now] = disl[now] = disr[now] = 0;
    return;
  }
  int mid = (l + r) / 2;
  if (k <= mid)
    update(l, mid, k, flag, now * 2);
  else
    update(mid + 1, r, k, flag, now * 2 + 1);
  pushUp(l, r, now);
}
long long query(int l, int r, int lef, int rig, int now) {
  if (lef <= l && r <= rig) {
    _num[now] = num[now];
    _sum[now] = sum[now];
    _disl[now] = disl[now];
    _disr[now] = disr[now];
    return sum[now];
  }
  int mid = (l + r) / 2;
  clean(now * 2);
  clean(now * 2 + 1);
  if (lef <= mid) query(l, mid, lef, rig, now * 2);
  if (rig > mid) query(mid + 1, r, lef, rig, now * 2 + 1);
  _pushUp(l, r, now);
  return _sum[now];
}
int main() {
  int n;
  cin >> n;
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    cin >> x[i];
    a[++cnt] = x[i];
  }
  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
    cin >> op[i].kind >> op[i].t1 >> op[i].t2;
    if (op[i].kind == 1) {
      a[op[i].t1] += op[i].t2;
      a[++cnt] = a[op[i].t1];
    }
  }
  for (int i = 1; i <= n; i++) a[i] = x[i];
  sort(a + 1, a + cnt + 1);
  for (int i = 1; i <= n; i++)
    f[lower_bound(a + 1, a + cnt + 1, x[i]) - a] = true;
  buildtree(1, cnt, 1);
  for (int i = 0; i < m; i++) {
    if (op[i].kind == 1) {
      int pre = lower_bound(a + 1, a + cnt + 1, x[op[i].t1]) - a;
      x[op[i].t1] += op[i].t2;
      int las = lower_bound(a + 1, a + cnt + 1, x[op[i].t1]) - a;
      update(1, cnt, pre, false, 1);
      update(1, cnt, las, true, 1);
    } else {
      int left = lower_bound(a + 1, a + cnt + 1, op[i].t1) - a;
      int right = upper_bound(a + 1, a + cnt + 1, op[i].t2) - a - 1;
      if (left > right || left > cnt || right < 1) {
        cout << 0 << endl;
        continue;
      }
      cout << query(1, cnt, left, right, 1) << endl;
    }
  }
  return 0;
}
