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 kMaxN = 100000, kMaxM = 100000;
int n, m, x[kMaxN], _x[kMaxN];
int seq[kMaxN + kMaxM + 1], idx;
struct Command {
  int a, b, c;
} cmd[kMaxM];
struct Info {
  int sz;
  long long sum, val;
  Info() {}
  Info(int sz_, long long sum_, long long val_)
      : sz(sz_), sum(sum_), val(val_) {}
};
Info operator+(const Info &a, const Info &b) {
  return Info(a.sz + b.sz, a.sum + b.sum,
              a.val + b.val + b.sum * a.sz - a.sum * b.sz);
}
struct Node {
  Info info;
  Node *son[2];
  void update() { info = son[0]->info + son[1]->info; }
} node_pool[2 * (kMaxN + kMaxM + 1) - 1], *node_idx = node_pool, *root = NULL;
Node *BuildTree(int l, int r) {
  Node *res = node_idx++;
  if (l + 1 < r) {
    int mid = (l + r) >> 1;
    res->son[0] = BuildTree(l, mid);
    res->son[1] = BuildTree(mid, r);
  }
  return res;
}
void Insert(int x, int d, int v, Node *pos, int pos_l, int pos_r) {
  if (pos_l + 1 == pos_r) {
    pos->info.sz += d;
    if (pos->info.sz == 1) pos->info.sum = v, pos->info.val = 0;
    if (pos->info.sz == 0) pos->info.sum = 0, pos->info.val = 0;
    return;
  }
  int mid = (pos_l + pos_r) >> 1;
  if (x < mid)
    Insert(x, d, v, pos->son[0], pos_l, mid);
  else
    Insert(x, d, v, pos->son[1], mid, pos_r);
  pos->update();
}
Info Query(int l, int r, Node *pos, int pos_l, int pos_r) {
  if (l <= pos_l && r >= pos_r) return pos->info;
  int mid = (pos_l + pos_r) >> 1;
  if (l >= mid) return Query(l, r, pos->son[1], mid, pos_r);
  if (r <= mid) return Query(l, r, pos->son[0], pos_l, mid);
  return Query(l, r, pos->son[0], pos_l, mid) +
         Query(l, r, pos->son[1], mid, pos_r);
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%d", &x[i]);
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    scanf("%d%d%d", &cmd[i].a, &cmd[i].b, &cmd[i].c);
    if (cmd[i].a == 1) --cmd[i].b;
  }
  memcpy(_x, x, sizeof(x));
  for (int i = 0; i < n; ++i) seq[idx++] = x[i];
  for (int i = 0; i < m; ++i)
    if (cmd[i].a == 1) {
      _x[cmd[i].b] += cmd[i].c;
      seq[idx++] = _x[cmd[i].b];
    }
  seq[idx++] = 2147483647;
  sort(seq, seq + idx);
  idx = unique(seq, seq + idx) - seq;
  root = BuildTree(0, idx);
  for (int i = 0; i < n; ++i)
    Insert(lower_bound(seq, seq + idx, x[i]) - seq, 1, x[i], root, 0, idx);
  for (int i = 0; i < m; ++i)
    if (cmd[i].a == 1) {
      Insert(lower_bound(seq, seq + idx, x[cmd[i].b]) - seq, -1, x[cmd[i].b],
             root, 0, idx);
      x[cmd[i].b] += cmd[i].c;
      Insert(lower_bound(seq, seq + idx, x[cmd[i].b]) - seq, 1, x[cmd[i].b],
             root, 0, idx);
    } else {
      int l = lower_bound(seq, seq + idx, cmd[i].b) - seq;
      int r = lower_bound(seq, seq + idx, cmd[i].c + 1) - seq;
      if (l < r)
        printf("%I64d\n", Query(l, r, root, 0, idx).val);
      else
        puts("0");
    }
  return 0;
}
