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;
template <typename T, typename Compare, int MaxNode>
class Splay {
 public:
  class node {
   public:
    node *c[2], *f;
    int siz, rev;
    T data;
    bool side() { return f->c[1] == this; }
    void setc(bool dir, node* A) {
      c[dir] = A;
      A->f = this;
    }
    void output() {
      if (siz == 0) return;
      c[0]->output();
      cerr << data.num << ' ';
      c[1]->output();
    }
  };
  node b[MaxNode + 2], *root;
  int len;
  Compare cmp;
  Splay() {
    len = 0;
    newnode();
    newnode();
    b[1].c[1] = b + 2;
    b[1].siz = 2;
    b[1].data.num = -1000000000000ll;
    root = b[2].f = b + 1;
    b[2].siz = 1;
    b[2].data.num = 1000000000000ll;
  }
  void rot(node* A) {
    bool dir = A->side();
    node* f = A->f;
    update(f);
    update(A);
    if (A->f == root)
      root = A, A->f = b;
    else
      f->f->setc(f->side(), A);
    f->setc(dir, A->c[!dir]);
    A->setc(!dir, f);
    update(f);
    update(A);
  }
  void splay(node* A, node* B) {
    if (A == B) throw "Splay node Same!";
    while (A->f != B) {
      if (A->f->f == B)
        rot(A);
      else if (A->side() == A->f->side())
        rot(A->f), rot(A);
      else
        rot(A), rot(A);
    }
  }
  node* newnode() {
    clear(b + (++len));
    return b + len;
  }
  void clear(node* now) {
    now->c[0] = now->c[1] = now->f = b;
    now->siz = 1;
    now->rev = 0;
    now->data.clear();
  }
  void update(node* now) {
    downmark(now);
    if (now->c[0] != b) downmark(now->c[0]);
    if (now->c[1] != b) downmark(now->c[1]);
    now->siz = now->c[0]->siz + now->c[1]->siz + 1;
    now->data.update(now->c[0]->data, now->c[1]->data, now->c[0]->siz,
                     now->c[1]->siz);
  }
  void downmark(node* now) {
    if (!now->rev) return;
    swap(now->c[0], now->c[1]);
    now->rev = 0;
    now->data.downmark(now->c[0]->data, now->c[1]->data);
  }
  node* next(node* now, bool dir) {
    splay(now, b);
    now = now->c[dir];
    while (now->c[!dir] != b) now = now->c[!dir];
    splay(now, b);
    return now;
  }
  node* find(int k) {
    k++;
    for (node* now = root;;) {
      if (now->c[0]->siz + 1 == k) return now;
      if (now->c[0]->siz + 1 <= k)
        k -= now->c[0]->siz + 1, now = now->c[1];
      else
        now = now->c[0];
    }
  }
  node* lower_bound(const T& x) {
    node *now = root, *ret = b + 2;
    while (now != b)
      if (!cmp(now->data, x))
        ret = now, now = now->c[0];
      else
        now = now->c[1];
    return ret;
  }
  node* upper_bound(const T& x) {
    node *now = root, *ret = b + 2;
    while (now != b)
      if (cmp(x, now->data))
        ret = now, now = now->c[0];
      else
        now = now->c[1];
    return ret;
  }
  node* insert(const T& x) {
    node *p, *q;
    p = lower_bound(x);
    q = next(p, 0);
    splay(q, b);
    splay(p, q);
    root->c[1]->c[0] = newnode();
    root->c[1]->c[0]->data = x;
    root->c[1]->c[0]->f = root->c[1];
    update(root->c[1]);
    update(root);
    return root->c[1]->c[0];
  }
  void erase(const T& x) {
    node *p, *q;
    p = lower_bound(x);
    q = next(p, 1);
    p = next(p, 0);
    splay(p, b);
    splay(q, p);
    root->c[1]->c[0] = b;
    update(root->c[1]);
    update(root);
  }
  node* getinter(node* p, node* q) {
    splay(p, b);
    splay(q, p);
    return root->c[1]->c[0];
  }
  void output() {
    root->output();
    cerr << endl;
  }
};
class arr {
 public:
  long long num;
  long long value, sum;
  void clear() {
    value = sum = 0;
    num = 0;
  }
  void downmark(arr& L, arr& R) {}
  void update(arr& L, arr& R, int sizL, int sizR) {
    value = L.value + R.value + sizL * R.sum - sizR * L.sum + R.sum -
            1ll * sizR * num - L.sum + 1ll * sizL * num;
    sum = L.sum + R.sum + num;
  }
};
class classcmp {
 public:
  bool operator()(const arr& a, const arr& b) const { return a.num < b.num; }
};
Splay<arr, classcmp, 200010> A;
int n, k, m, type, L, R;
Splay<arr, classcmp, 200010>::node* a[100010];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &k);
    arr nxt;
    nxt.sum = nxt.num = k;
    nxt.value = 0;
    a[i] = A.insert(nxt);
  }
  for (scanf("%d", &m); m--;) {
    scanf("%d%d%d", &type, &L, &R);
    if (type == 1) {
      Splay<arr, classcmp, 200010>::node* x = A.lower_bound(a[L]->data);
      arr nxt;
      nxt.sum = nxt.num = x->data.num + R;
      nxt.value = 0;
      A.erase(x->data);
      a[L] = A.insert(nxt);
    } else {
      Splay<arr, classcmp, 200010>::node *p, *q;
      arr LL, RR;
      LL.sum = LL.num = L;
      RR.sum = RR.num = R;
      p = A.lower_bound(LL);
      q = A.upper_bound(RR);
      p = A.next(p, 0);
      cout << A.getinter(p, q)->data.value << endl;
    }
  }
  return 0;
}
