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;
struct Treap {
  struct Node {
    int x, fix;
    long long size, ll, rr;
    long long lsum, rsum, dist;
    Node *left, *right;
    Node() {}
    Node(int _x, Node *l = NULL, Node *r = NULL) {
      x = _x, left = l, right = r, fix = rand(), size = 1;
      ll = rr = x, lsum = 0, rsum = 0, dist = 0;
    }
    void pushup() {
      if (!left && !right) {
        size = 1, ll = rr = x, lsum = rsum = dist = 0;
        return;
      }
      size = 1;
      if (left) size += left->size;
      if (right) size += right->size;
      ll = rr = x;
      if (left) ll = left->ll;
      if (right) rr = right->rr;
      lsum = rsum = 0;
      if (!right) {
        lsum = left->lsum + x - left->ll;
        rsum = left->rsum + left->size * (x - left->rr);
      } else if (!left) {
        lsum = right->lsum + right->size * (right->ll - x);
        rsum = right->rsum + right->rr - x;
      } else {
        lsum = left->lsum + x - left->ll + right->lsum +
               right->size * (right->ll - left->ll);
        rsum = right->rsum + right->rr - x + left->rsum +
               left->size * (right->rr - left->rr);
      }
      dist = 0;
      if (left) dist += left->dist + left->rsum + left->size * (x - left->rr);
      if (right)
        dist += right->dist + right->lsum + right->size * (right->ll - x);
      if (left && right) {
        dist += right->size * left->rsum + left->size * right->lsum;
        dist += (right->ll - left->rr) * left->size * right->size;
      }
    }
  } * T;
  typedef pair<Node *, Node *> pnn;
  void init() { T = NULL; }
  Node *merge(Node *l, Node *r) {
    if (!l || !r) return l ? l : r;
    if (l->fix < r->fix) {
      l->right = merge(l->right, r);
      l->pushup();
      return l;
    } else {
      r->left = merge(l, r->left);
      r->pushup();
      return r;
    }
  }
  pnn split(Node *T, int val) {
    if (!T) return pnn(NULL, NULL);
    if (val < T->x) {
      pnn t = split(T->left, val);
      T->left = t.second, T->pushup();
      return make_pair(t.first, T);
    } else {
      pnn t = split(T->right, val);
      T->right = t.first, T->pushup();
      return make_pair(T, t.second);
    }
  }
  void insert(int x) {
    pnn t = split(T, x - 1);
    T = merge(t.first, merge(new Node(x), t.second));
  }
  void erase(int x) {
    pnn t1 = split(T, x - 1), t2 = split(t1.second, x);
    delete t2.first;
    T = merge(t1.first, t2.second);
  }
  long long query(int l, int r) {
    pnn t1 = split(T, l - 1), t2 = split(t1.second, r);
    long long ans = t2.first ? t2.first->dist : 0;
    T = merge(t1.first, merge(t2.first, t2.second));
    return ans;
  }
  void print(Node *T, string s = "    ") {
    if (!T) {
      cout << s << "NULL" << endl;
      return;
    }
    cout << s << "x:" << T->x << endl;
    cout << s << "  size:" << T->size << endl;
    cout << s << "  dist:" << T->dist << endl;
    cout << s << "  lsum:" << T->lsum << endl;
    cout << s << "  rsum:" << T->rsum << endl;
    cout << s << "  ll & rr:" << T->ll << " " << T->rr << endl;
    cout << s << "  lson:" << endl;
    print(T->left, s + "  ");
    cout << s << "  rson:" << endl;
    print(T->right, s + "  ");
  }
} T;
int a[100010];
int main() {
  srand(232373);
  int n;
  scanf("%d", &n);
  T.init();
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    T.insert(a[i]);
  }
  int q;
  scanf("%d", &q);
  while (q--) {
    int op, x, y;
    scanf("%d%d%d", &op, &x, &y);
    if (op == 1)
      T.erase(a[x]), a[x] += y, T.insert(a[x]);
    else
      printf("%I64d\n", T.query(x, y));
  }
  return 0;
}
