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 oo = 0x3f3f3f3f;
const int MAX_N = 100005;
const int MAX_M = 100005;
struct Operation {
  int type, x, y;
  Operation() {}
  Operation(int type, int x, int y) {
    this->type = type;
    this->x = x;
    this->y = y;
  }
};
struct Node {
  int size;
  long long sum, pairSums;
  Node() { size = sum = pairSums = 0; }
};
int N, Position[MAX_N], MaxX, M;
Operation O[MAX_M];
vector<int> X;
Node Tree[8 * MAX_N];
inline int LowerBound(int x) {
  int left = 0, right = MaxX;
  int position = -1;
  while (left <= right) {
    int middle = (left + right) / 2;
    if (x <= X[middle]) {
      right = middle - 1;
      position = middle;
    } else {
      left = middle + 1;
    }
  }
  return position;
}
inline int UpperBound(int x) {
  int left = 0, right = MaxX;
  int position = -1;
  while (left <= right) {
    int middle = (left + right) / 2;
    if (X[middle] <= x) {
      left = middle + 1;
      position = middle;
    } else {
      right = middle - 1;
    }
  }
  return position;
}
void Normalize() {
  for (int i = 1; i <= N; ++i) X.push_back(Position[i]);
  for (int i = 1; i <= M; ++i) {
    if (O[i].type == 1) {
      Position[O[i].x] += O[i].y;
      X.push_back(Position[O[i].x]);
    }
  }
  for (int i = M; i > 0; --i)
    if (O[i].type == 1) Position[O[i].x] -= O[i].y;
  sort(X.begin(), X.end());
  X.erase(unique(X.begin(), X.end()), X.end());
  MaxX = static_cast<int>(X.size()) - 1;
}
inline Node Merge(const Node &left, const Node &right) {
  Node result;
  result.size = left.size + right.size;
  result.sum = left.sum + right.sum;
  result.pairSums = left.pairSums + right.pairSums + right.sum * left.size -
                    left.sum * right.size;
  return result;
}
void Update(int node, int left, int right, int position, int value) {
  int middle = (left + right) / 2;
  if (left == right) {
    Tree[node].size += value;
    Tree[node].sum = 1LL * Tree[node].size * X[position];
    Tree[node].pairSums = 0;
    return;
  }
  if (position <= middle)
    Update(2 * node, left, middle, position, value);
  else
    Update(2 * node + 1, middle + 1, right, position, value);
  Tree[node] = Merge(Tree[2 * node], Tree[2 * node + 1]);
}
Node Query(int node, int left, int right, int qLeft, int qRight) {
  int middle = (left + right) / 2;
  if (qLeft <= left && right <= qRight) return Tree[node];
  Node result;
  if (qLeft <= middle)
    result = Merge(result, Query(2 * node, left, middle, qLeft, qRight));
  if (qRight > middle)
    result =
        Merge(result, Query(2 * node + 1, middle + 1, right, qLeft, qRight));
  return result;
}
void Solve() {
  Normalize();
  for (int i = 1; i <= N; ++i) {
    int x = LowerBound(Position[i]);
    Update(1, 0, MaxX, x, 1);
  }
  for (int i = 1; i <= M; ++i) {
    if (O[i].type == 1) {
      int x = LowerBound(Position[O[i].x]);
      Update(1, 0, MaxX, x, -1);
      Position[O[i].x] += O[i].y;
      x = LowerBound(Position[O[i].x]);
      Update(1, 0, MaxX, x, 1);
    } else {
      if (O[i].x > O[i].y || O[i].x > X[MaxX] || O[i].y < X[0]) {
        cout << "0\n";
      } else {
        int left = LowerBound(O[i].x), right = UpperBound(O[i].y);
        Node result = Query(1, 0, MaxX, left, right);
        cout << result.pairSums << "\n";
      }
    }
  }
}
void Read() {
  cin >> N;
  for (int i = 1; i <= N; ++i) cin >> Position[i];
  cin >> M;
  for (int i = 1; i <= M; ++i) cin >> O[i].type >> O[i].x >> O[i].y;
}
int main() {
  Read();
  Solve();
  return 0;
}
