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 = 1e5 + 10, SN = 1e6 + 10;
vector<long long> xs;
vector<int> ans;
long long dis_beg[SN], dis_end[SN], dis_dak[SN], cnt[SN], x[N], X[N];
int l[SN], r[SN], n, m;
struct tup {
  int typ, l, r;
};
vector<tup> query;
int comp(long long p) {
  vector<long long>::iterator it = lower_bound(xs.begin(), xs.end(), p);
  return (int)(it - xs.begin());
}
void update(int v, int lc, int rc) {
  int nv = N * 4 + 4;
  dis_beg[nv] = dis_beg[lc] + dis_beg[rc] + (cnt[rc] * (xs[r[lc]] - xs[l[lc]]));
  dis_end[nv] = dis_end[lc] + dis_end[rc] + (cnt[lc] * (xs[r[rc]] - xs[l[rc]]));
  dis_dak[nv] =
      dis_dak[lc] + dis_dak[rc] + dis_end[lc] * cnt[rc] + cnt[lc] * dis_beg[rc];
  cnt[nv] = cnt[lc] + cnt[rc];
  dis_beg[v] = dis_beg[nv];
  dis_end[v] = dis_end[nv];
  dis_dak[v] = dis_dak[nv];
  cnt[v] = cnt[nv];
}
void make(int v, int sl, int sr) {
  l[v] = sl;
  r[v] = sr;
  if (r[v] - l[v] == 1) return;
  int med = (sl + sr) / 2;
  make(2 * v, sl, med);
  make(2 * v + 1, med, sr);
}
void del(int v, int i) {
  if (r[v] - l[v] == 1) {
    dis_beg[v] = 0;
    dis_end[v] = 0;
    dis_dak[v] = 0;
    cnt[v] = 0;
    return;
  }
  int med = (l[v] + r[v]) / 2;
  if (i < med)
    del(2 * v, i);
  else
    del(2 * v + 1, i);
  update(v, 2 * v, 2 * v + 1);
}
void add(int v, int i) {
  if (r[v] - l[v] == 1) {
    dis_beg[v] = 0;
    dis_end[v] = xs[r[v]] - xs[l[v]];
    dis_dak[v] = 0;
    cnt[v] = 1;
    return;
  }
  int med = (l[v] + r[v]) / 2;
  if (i < med)
    add(2 * v, i);
  else
    add(2 * v + 1, i);
  update(v, 2 * v, 2 * v + 1);
}
void get(int v, int ql, int qr) {
  if (ql >= r[v] || qr <= l[v]) return;
  if (ql <= l[v] && r[v] <= qr) {
    ans.push_back(v);
    return;
  }
  get(2 * v, ql, qr);
  get(2 * v + 1, ql, qr);
}
long long getAns(int ql, int qr) {
  get(1, ql, qr);
  int u = 4 * N + 5;
  dis_beg[u] = 0;
  dis_end[u] = 0;
  dis_dak[u] = 0;
  cnt[u] = 0;
  for (int v : ans) update(u, u, v);
  if (!ans.empty()) ans.clear();
  return dis_dak[u];
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> x[i];
    x[i]--;
    X[i] = x[i];
    xs.push_back(x[i]);
  }
  cin >> m;
  for (int i = 0; i < m; i++) {
    tup q;
    cin >> q.typ >> q.l >> q.r;
    if (q.typ == 1) {
      q.l--;
      x[q.l] += q.r;
      xs.push_back(x[q.l]);
      q.r = x[q.l];
    } else
      q.l--;
    query.push_back(q);
  }
  sort(xs.begin(), xs.end());
  xs.resize(distance(xs.begin(), unique(xs.begin(), xs.end())));
  make(1, 0, (int)xs.size());
  for (int i = 0; i < n; i++) X[i] = comp(X[i]), add(1, X[i]);
  for (tup q : query) {
    if (q.typ == 1) {
      del(1, X[q.l]);
      X[q.l] = comp(q.r);
      add(1, X[q.l]);
    } else {
      cout << getAns(comp(q.l), comp(q.r)) << '\n';
    }
  }
}
