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 vertex {
  long long sum, dist;
  int cnt;
  vertex(long long sum, long long dist, int cnt) {
    this->sum = sum;
    this->dist = dist;
    this->cnt = cnt;
  }
  vertex() { sum = dist = cnt = 0; }
};
int x[100100];
int b[100100];
int ty[100100];
int l[100100];
int r[100100];
vector<int> a;
vertex t[2000010];
int k;
vertex merge(vertex a, vertex b) {
  vertex res;
  res.sum = a.sum + b.sum;
  res.cnt = a.cnt + b.cnt;
  res.dist = b.sum * a.cnt - a.sum * b.cnt + a.dist + b.dist;
  return res;
}
void mod(int p, vertex v) {
  p += k - 1;
  t[p] = v;
  p >>= 1;
  while (p) {
    t[p] = merge(t[p + p], t[p + p + 1]);
    p >>= 1;
  }
}
vertex find(int l, int r, int L, int R, int v) {
  if ((l == L) && (r == R)) return t[v];
  int m = (L + R) / 2;
  if (r <= m) return find(l, r, L, m, v + v);
  if (l > m) return find(l, r, m + 1, R, v + v + 1);
  return merge(find(l, m, L, m, v + v), find(m + 1, r, m + 1, R, v + v + 1));
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = (0); i < (n); ++i) {
    scanf("%d", &x[i]);
    b[i] = x[i];
    a.push_back(x[i]);
  }
  int m;
  scanf("%d", &m);
  for (int i = (0); i < (m); ++i) {
    scanf("%d%d%d", &ty[i], &l[i], &r[i]);
    if (ty[i] == 1) {
      b[l[i] - 1] += r[i];
      a.push_back(b[l[i] - 1]);
    } else {
      a.push_back(l[i]);
      a.push_back(r[i]);
    }
  }
  sort(a.begin(), a.end());
  a.resize(unique(a.begin(), a.end()) - a.begin());
  k = 1;
  while (k < a.size()) k += k;
  for (int i = (0); i < (n); ++i) {
    int v = lower_bound(a.begin(), a.end(), x[i]) - a.begin();
    vertex ver = *new vertex(x[i], 0, 1);
    mod(v + 1, ver);
  }
  for (int i = (0); i < (m); ++i) {
    if (ty[i] == 1) {
      int v = lower_bound(a.begin(), a.end(), x[l[i] - 1]) - a.begin();
      mod(v + 1, *new vertex());
      x[l[i] - 1] += r[i];
      v = lower_bound(a.begin(), a.end(), x[l[i] - 1]) - a.begin();
      vertex ver = *new vertex(x[l[i] - 1], 0, 1);
      mod(v + 1, ver);
    } else {
      int l1 = lower_bound(a.begin(), a.end(), l[i]) - a.begin();
      int r1 = lower_bound(a.begin(), a.end(), r[i]) - a.begin();
      vertex v = find(l1 + 1, r1 + 1, 1, k, 1);
      printf("%I64d\n", v.dist);
    }
  }
  return 0;
}
