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 N = 3e5 + 5;
int n, x[N], t[N], y[N], a[N], b[N], m;
vector<int> vec;
struct node {
  long long sum = 0, cnt = 0, ans = 0;
  void merge(node a, node b) {
    cnt = a.cnt + b.cnt;
    sum = a.sum + b.sum;
    ans = a.ans + b.ans + b.sum * a.cnt - a.sum * b.cnt;
  }
} seg[N << 2];
void update(int x, int val = 1, int s = 0, int e = N, int id = 1) {
  if (e - s == 1) {
    seg[id].cnt += val;
    seg[id].sum += val * vec[x];
    return;
  }
  int mid = s + e >> 1;
  x < mid ? update(x, val, s, mid, id << 1)
          : update(x, val, mid, e, id << 1 | 1);
  seg[id].merge(seg[id << 1], seg[id << 1 | 1]);
}
node get(int l, int r, int s = 0, int e = N, int id = 1) {
  if (l <= s && e <= r) return seg[id];
  node res;
  if (l >= e || s >= r) return res;
  int mid = e + s >> 1;
  res.merge(get(l, r, s, mid, id << 1), get(l, r, mid, e, id << 1 | 1));
  return res;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> x[i];
    vec.push_back(y[i] = x[i]);
  }
  cin >> m;
  for (int i = 0, t1, t2; i < m; i++) {
    cin >> t[i] >> t1 >> t2;
    if (t[i] & 1) {
      a[i] = y[--t1];
      vec.push_back(b[i] = (y[t1] += t2));
    } else {
      vec.push_back(a[i] = t1);
      vec.push_back(b[i] = t2);
    }
  }
  vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
  sort(vec.begin(), vec.end());
  for (int i = 0; i < n; i++)
    x[i] = lower_bound(vec.begin(), vec.end(), x[i]) - vec.begin();
  for (int i = 0; i < m; i++) {
    a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
    b[i] = lower_bound(vec.begin(), vec.end(), b[i]) - vec.begin();
  }
  for (int i = 0; i < n; i++) update(x[i]);
  for (int i = 0; i < m; i++) {
    if (t[i] & 1)
      update(a[i], -1), update(b[i]);
    else
      cout << get(a[i], b[i] + 1).ans << endl;
  }
}
