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 State {
  long long cnt;
  long long left;
  long long right;
  long long res;
  State() : cnt(0), left(0), right(0), res(0) {}
  State(long long cnt, long long left, long long right, long long res)
      : cnt(cnt), left(left), right(right), res(res) {}
};
int A[1 << 18];
int T[1 << 18];
int L[1 << 18];
int R[1 << 18];
long long X[1 << 18];
long long Z[1 << 18];
State RMQ[2 << 18];
int I[18 + 1];
void update(int level, int pos, int a, int value) {
  int from = pos << level;
  int to = (pos + 1) << level;
  if (a < from || to <= a) return;
  State& parent = RMQ[I[level] + pos];
  if (level == 0) {
    parent.cnt = value;
    parent.left = 0;
    parent.right = value * (Z[a + 1] - Z[a]);
    parent.res = 0;
    return;
  }
  int mid = (to + from) >> 1;
  update(level - 1, pos + pos, a, value);
  update(level - 1, pos + pos + 1, a, value);
  State& left = RMQ[I[level - 1] + pos + pos];
  State& right = RMQ[I[level - 1] + pos + pos + 1];
  parent.cnt = left.cnt + right.cnt;
  parent.left = left.left + right.left + right.cnt * (Z[mid] - Z[from]);
  parent.right = right.right + left.right + left.cnt * (Z[to] - Z[mid]);
  parent.res =
      left.res + right.res + left.right * right.cnt + right.left * left.cnt;
}
State find(int level, int pos, int a, int b) {
  int from = pos << level;
  int to = (pos + 1) << level;
  if (b <= from || to <= a) return State();
  if (a <= from && to <= b) return RMQ[I[level] + pos];
  int mid = (to + from) >> 1;
  State left = find(level - 1, pos + pos, a, b);
  State right = find(level - 1, pos + pos + 1, a, b);
  return State(
      left.cnt + right.cnt,
      left.left + right.left + right.cnt * (Z[mid] - Z[from]),
      right.right + left.right + left.cnt * (Z[to] - Z[mid]),
      left.res + right.res + left.right * right.cnt + right.left * left.cnt);
}
int main() {
  int n;
  scanf("%d", &n);
  int i;
  for (i = (0); i < (n); ++i) scanf("%d", &A[i]);
  int m;
  scanf("%d", &m);
  for (i = (0); i < (m); ++i) scanf("%d%d%d", &T[i], &L[i], &R[i]);
  vector<long long> x;
  for (i = (0); i < (n); ++i) {
    X[i] = A[i];
    x.push_back(X[i]);
  }
  for (i = (0); i < (m); ++i)
    if (T[i] == 1) {
      int a = L[i] - 1;
      X[a] += R[i];
      x.push_back(X[a]);
    }
  sort((x).begin(), (x).end());
  x.resize(unique((x).begin(), (x).end()) - x.begin());
  int cnt = int((x).size());
  for (i = (0); i < (cnt); ++i) Z[i] = x[i];
  Z[cnt] = Z[cnt - 1];
  I[0] = 0;
  for (i = (0); i < (18); ++i) I[i + 1] = I[i] + (1 << (18 - i));
  for (i = (0); i < (n); ++i) {
    X[i] = A[i];
    int a = lower_bound((x).begin(), (x).end(), X[i]) - x.begin();
    update(18, 0, a, 1);
  }
  for (i = (0); i < (m); ++i)
    if (T[i] == 1) {
      int a = L[i] - 1;
      int b = lower_bound((x).begin(), (x).end(), X[a]) - x.begin();
      update(18, 0, b, 0);
      X[a] += R[i];
      b = lower_bound((x).begin(), (x).end(), X[a]) - x.begin();
      update(18, 0, b, 1);
    } else {
      int a = lower_bound((x).begin(), (x).end(), L[i]) - x.begin();
      int b = lower_bound((x).begin(), (x).end(), R[i] + 1) - x.begin();
      printf("%lld\n", find(18, 0, a, b).res);
    }
  return 0;
};
