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 long long maxn = 1e5 + 5;
long long seg[16 * maxn], pref[16 * maxn], suff[16 * maxn], t[16 * maxn],
    X[maxn], Y[maxn], type[maxn], a[maxn], tmp[maxn];
vector<long long> compress;
map<long long, long long> M;
struct Get {
  long long t = 0, seg = 0, suff = 0, pref = 0, dist = 0;
};
void add(long long id, long long L, long long R, long long idx, long long x) {
  if (idx < L || idx >= R) return;
  if (R == L + 1) {
    t[id] += x;
    suff[id] += x * (compress[R] - compress[idx]);
    return;
  }
  long long mid = (L + R) / 2;
  add(2 * id + 0, L, mid, idx, x);
  add(2 * id + 1, mid, R, idx, x);
  t[id] = t[2 * id] + t[2 * id + 1];
  pref[id] = pref[2 * id] + pref[2 * id + 1] +
             t[2 * id + 1] * (compress[mid] - compress[L]);
  suff[id] = suff[2 * id + 1] + suff[2 * id] +
             t[2 * id] * (compress[R] - compress[mid]);
  seg[id] = seg[2 * id] + seg[2 * id + 1] + t[2 * id] * pref[2 * id + 1] +
            t[2 * id + 1] * suff[2 * id];
}
Get get(long long id, long long L, long long R, long long l, long long r) {
  Get ans;
  if (R <= l || r <= L) return ans;
  if (L >= l && R <= r) {
    ans.seg = seg[id];
    ans.t = t[id];
    ans.pref = pref[id];
    ans.suff = suff[id];
    ans.dist = compress[R] - compress[L];
    return ans;
  }
  long long mid = (L + R) / 2;
  Get P = get(2 * id + 0, L, mid, l, r);
  Get Q = get(2 * id + 1, mid, R, l, r);
  ans.t = P.t + Q.t;
  ans.dist = P.dist + Q.dist;
  ans.pref = P.pref + Q.pref + Q.t * P.dist;
  ans.suff = Q.suff + P.suff + P.t * Q.dist;
  ans.seg = P.seg + Q.seg + P.t * Q.pref + Q.t * P.suff;
  return ans;
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n;
  cin >> n;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
    tmp[i] = a[i];
    compress.push_back(a[i]);
  }
  long long m;
  cin >> m;
  for (long long i = 0; i < m; i++) {
    cin >> type[i] >> X[i] >> Y[i];
    if (type[i] == 1) {
      X[i]--;
      tmp[X[i]] += Y[i];
      compress.push_back(tmp[X[i]]);
    } else {
      compress.push_back(X[i]);
      compress.push_back(Y[i]);
    }
  }
  compress.push_back(-1e9);
  compress.push_back(1e9);
  sort(compress.begin(), compress.end());
  compress.resize(unique(compress.begin(), compress.end()) - compress.begin());
  long long sz = compress.size();
  for (long long i = 0; i < sz; i++) {
    M[compress[i]] = i;
  }
  for (long long i = 0; i < n; i++) {
    tmp[i] = a[i];
    a[i] = M[a[i]];
    add(1, 0, sz, a[i], +1);
  }
  for (long long i = 0; i < m; i++) {
    if (type[i] == 1) {
      tmp[X[i]] += Y[i];
      Y[i] = M[tmp[X[i]]];
      add(1, 0, sz, a[X[i]], -1);
      add(1, 0, sz, Y[i], +1);
      a[X[i]] = Y[i];
    } else {
      X[i] = M[X[i]];
      Y[i] = M[Y[i]];
      cout << get(1, 0, sz, X[i], Y[i] + 1).seg << '\n';
    }
  }
}
