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>
#pragma comment(linker, "/STACK:66777216")
using namespace std;
inline void add(pair<long long, int> &a, pair<long long, int> b) {
  a.first += b.first;
  a.second += b.second;
}
struct T {
  int n;
  vector<pair<long long, int> > tr;
  long long sum;
  inline void reset(int _n) {
    n = _n;
    tr.clear();
    tr.resize(n + 1);
    tr.assign((int)((tr).size()), make_pair(0LL, 0));
    sum = 0;
  }
  inline void upd(int first, pair<long long, int> val) {
    for (; first <= n; first |= first + 1) add(tr[first], val);
  }
  inline pair<long long, int> fnd(int first) {
    pair<long long, int> ans = make_pair(0LL, 0);
    for (; first >= 0; first = (first & (first + 1)) - 1) add(ans, tr[first]);
    return ans;
  }
  inline pair<long long, int> fnd(int l, int r) {
    pair<long long, int> t = fnd(r);
    pair<long long, int> t2 = fnd(l - 1);
    t.first -= t2.first;
    t.second -= t2.second;
    return t;
  }
};
int a, b, c, d, i, j, n, m, k;
T tr[524288 + 2];
int nx[200002], mas[100002], beg[100002], lx;
pair<int, pair<int, int> > quer[100002];
void build(int l, int r, int v) {
  tr[v].reset(r - l);
  if (l == r - 1) return;
  int xx = (r + l) / 2;
  build(l, xx, v * 2);
  build(xx, r, v * 2 + 1);
}
void upd(int l, int r, int first, pair<long long, int> val, int v) {
  pair<long long, int> lf = tr[v].fnd(first - l - 1);
  pair<long long, int> rt = tr[v].fnd(first - l + 1, r - l);
  long long add =
      lf.second * val.first - lf.first + rt.first - rt.second * val.first;
  tr[v].sum += add * val.second;
  if (val.second == -1) {
    val.first = -val.first;
  }
  tr[v].upd(first - l, val);
  if (val.second == -1) {
    val.first = -val.first;
  }
  if (l == r - 1) return;
  int xx = (r + l) / 2;
  if (first < xx)
    upd(l, xx, first, val, v * 2);
  else
    upd(xx, r, first, val, v * 2 + 1);
}
long long fnd(int l, int r, int a, int b, vector<pair<long long, int> > &cov,
              int v) {
  if (l == a && b == r - 1) {
    cov.push_back(tr[v].fnd(r - l));
    return tr[v].sum;
  }
  int xx = (r + l) / 2;
  if (b < xx)
    return fnd(l, xx, a, b, cov, v * 2);
  else if (a >= xx)
    return fnd(xx, r, a, b, cov, v * 2 + 1);
  else {
    long long ans = fnd(l, xx, a, xx - 1, cov, v * 2);
    ans += fnd(xx, r, xx, b, cov, v * 2 + 1);
    return ans;
  }
}
int main() {
  scanf("%d", &n);
  for (int _n((n)-1), i(0); i <= _n; i++) {
    scanf("%d", &mas[i]);
    nx[lx++] = mas[i];
    beg[i] = mas[i];
  }
  scanf("%d", &m);
  for (int _n((m)-1), i(0); i <= _n; i++) {
    scanf("%d%d%d", &quer[i].first, &quer[i].second.first,
          &quer[i].second.second);
    if (quer[i].first == 1) {
      --quer[i].second.first;
      mas[quer[i].second.first] += quer[i].second.second;
      nx[lx++] = mas[quer[i].second.first];
    }
  }
  sort(nx, nx + lx);
  lx = unique(nx, nx + lx) - nx;
  build(0, lx, 1);
  for (int _n((n)-1), i(0); i <= _n; i++) {
    int t = lower_bound(nx, nx + lx, beg[i]) - nx;
    upd(0, lx, t, make_pair((long long)beg[i], 1), 1);
  }
  memcpy(mas, beg, sizeof(mas));
  for (int _n((m)-1), i(0); i <= _n; i++) {
    if (quer[i].first == 1) {
      int v = quer[i].second.first;
      int old = lower_bound(nx, nx + lx, mas[v]) - nx;
      upd(0, lx, old, make_pair((long long)mas[v], -1), 1);
      mas[v] += quer[i].second.second;
      int nw = lower_bound(nx, nx + lx, mas[v]) - nx;
      upd(0, lx, nw, make_pair((long long)mas[v], 1), 1);
    } else {
      int l = lower_bound(nx, nx + lx, quer[i].second.first) - nx;
      int r = upper_bound(nx, nx + lx, quer[i].second.second) - nx - 1;
      if (l > r) {
        printf("0\n");
        continue;
      }
      vector<pair<long long, int> > cover;
      long long ans = fnd(0, lx, l, r, cover, 1);
      for (int _n(((int)((cover).size())) - 1), j(0); j <= _n; j++) {
        for (int _n((int)((cover).size()) - 1), z(j + 1); z <= _n; z++) {
          ans += (long long)cover[z].first * cover[j].second -
                 (long long)cover[j].first * cover[z].second;
        }
      }
      printf("%I64d\n", ans);
    }
  }
}
