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 trie {
  int x, p;
  int cnt;
  long long sum, res;
  trie *l, *r;
};
long long getcnt(trie* cur) {
  if (cur) return cur->cnt;
  return 0;
}
long long getsum(trie* cur) {
  if (cur) return cur->sum;
  return 0;
}
long long getres(trie* cur) {
  if (cur) return cur->res;
  return 0;
}
const int SZ = 100001;
trie nodes[SZ];
int x[SZ];
map<int, int> used;
int iter = 0;
int usd[1000000];
void check(trie* cur) {
  if (!cur) return;
  if (usd[cur - &nodes[0]] == iter) {
    while (1) {
      printf("BAD\n");
    }
  }
  usd[cur - &nodes[0]] = iter;
  check(cur->l);
  check(cur->r);
}
void update(trie* cur) {
  if (cur) {
    cur->cnt = 1 + getcnt(cur->l) + getcnt(cur->r);
    cur->sum = cur->x + getsum(cur->l) + getsum(cur->r);
    cur->res = cur->x * getcnt(cur->l) - cur->x * getcnt(cur->r) +
               getres(cur->l) + getres(cur->r) -
               getsum(cur->l) * (getcnt(cur->r) + 1) +
               getsum(cur->r) * (getcnt(cur->l) + 1);
  }
}
void split(trie* cur, trie*& l, trie*& r, int x) {
  if (!cur) {
    l = NULL;
    r = NULL;
  } else if (cur->x >= x) {
    r = cur;
    split(cur->l, l, r->l, x);
  } else {
    l = cur;
    split(cur->r, l->r, r, x);
  }
  update(l);
  update(r);
}
trie* merge(trie* l, trie* r) {
  trie* res;
  if (!l)
    res = r;
  else if (!r)
    res = l;
  else if (l->p > r->p) {
    res = l;
    res->r = merge(l->r, r);
  } else {
    res = r;
    res->l = merge(l, r->l);
  }
  update(res);
  return res;
}
void insert(trie*& cur, trie* node) {
  if (!cur) {
    cur = node;
    cur->l = cur->r = NULL;
  } else if (cur->p < node->p) {
    split(cur, node->l, node->r, node->x);
    cur = node;
  } else if (cur->x < node->x)
    insert(cur->r, node);
  else
    insert(cur->l, node);
  update(cur);
}
void erase(trie*& cur, int x) {
  if (!cur) {
    printf("BAD!");
    exit(0);
  } else if (cur->x == x) {
    cur = merge(cur->l, cur->r);
  } else if (cur->x < x)
    erase(cur->r, x);
  else
    erase(cur->l, x);
  update(cur);
}
int main() {
  int n;
  scanf("%d", &n);
  trie* top = NULL;
  for (int i = 0; i < (n); i++) {
    scanf("%d", &nodes[i].x);
    x[i] = nodes[i].x;
    used[x[i]] = 1;
    nodes[i].p = rand();
    nodes[i].l = NULL;
    nodes[i].r = NULL;
    ++iter;
    update(nodes + i);
    insert(top, &nodes[i]);
  }
  int m;
  scanf("%d", &m);
  for (int i = 0; i < (m); i++) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int p, d;
      scanf("%d%d", &p, &d);
      p--;
      erase(top, x[p]);
      nodes[p].l = NULL;
      nodes[p].r = NULL;
      x[p] += d;
      nodes[p].x += d;
      insert(top, &nodes[p]);
    } else {
      int l, r;
      scanf("%d%d", &l, &r);
      trie *a, *b, *c;
      split(top, a, b, l);
      split(b, b, c, r + 1);
      long long res = getres(b);
      cout << res << endl;
      a = merge(a, b);
      top = merge(a, c);
    }
  }
}
