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;
using ll = long long;
using ld = double;
const ll MODBASE = 1000000007LL;
const int MAXN = 100010;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
struct OrdinaryTreap {
  struct node {
    ll sum, res;
    int key;
    int prior, sz;
    node *l, *r;
    node(int _key = 0) {
      key = _key;
      sum = _key;
      res = 0;
      prior = rnd();
      sz = 1;
      l = r = NULL;
    }
  };
  typedef node *pnode;
  pnode root;
  void clear() { root = NULL; }
  OrdinaryTreap() { clear(); }
  int size(pnode it) { return it ? it->sz : 0; }
  ll getSum(pnode it) { return it ? it->sum : 0; }
  ll getRes(pnode it) { return it ? it->res : 0; }
  void recalc(pnode it) {
    if (it) {
      it->sz = size(it->l) + size(it->r) + 1;
      it->sum = it->key + getSum(it->l) + getSum(it->r);
      it->res = getRes(it->l) + getRes(it->r) + getSum(it->r) * size(it->l) -
                getSum(it->l) * size(it->r) + (ll)size(it->l) * it->key -
                getSum(it->l) + getSum(it->r) - (ll)size(it->r) * it->key;
    }
  }
  void merge(pnode &t, pnode l, pnode r) {
    if (!l || !r)
      t = l ? l : r;
    else if (l->prior > r->prior)
      merge(l->r, l->r, r), t = l;
    else
      merge(r->l, l, r->l), t = r;
    recalc(t);
  }
  void split(pnode t, pnode &l, pnode &r, ll key) {
    if (!t) {
      l = r = NULL;
      return;
    }
    if (key <= t->key)
      split(t->l, l, t->l, key), r = t;
    else
      split(t->r, t->r, r, key), l = t;
    recalc(t);
  }
  void insert(pnode &t, pnode it) {
    if (!t)
      t = it;
    else if (it->prior > t->prior)
      split(t, it->l, it->r, it->key), t = it;
    else
      insert(it->key < t->key ? t->l : t->r, it);
    recalc(t);
  }
  void insert(int u) {
    pnode w = new node(u);
    insert(root, w);
  }
  void remove(pnode &t, int key) {
    if (!t) return;
    if (key == t->key)
      merge(t, t->l, t->r);
    else
      remove(key < t->key ? t->l : t->r, key);
    recalc(t);
  }
  void remove(int pos) { return remove(root, pos); }
  ll query(int qL, int qR) {
    pnode l, r, mid;
    split(root, l, r, qL);
    split(r, mid, r, qR + 1);
    ll res = getRes(mid);
    merge(r, mid, r);
    merge(root, l, r);
    return res;
  }
};
int n, a[MAXN];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  cin >> n;
  for (int i = (1); i <= (n); i++) cin >> a[i];
  OrdinaryTreap tr;
  for (int i = (1); i <= (n); i++) tr.insert(a[i]);
  int q;
  cin >> q;
  while (q--) {
    int ch, u, v;
    cin >> ch >> u >> v;
    if (ch == 1) {
      tr.remove(a[u]);
      a[u] += v;
      tr.insert(a[u]);
    } else {
      cout << tr.query(u, v) << "\n";
    }
  }
  return 0;
}
