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>
const int kMaxPointsNum = 1 << 18;
const int kMaxIntervals = 1 << 19;
const int kMaxOperations = 5 * 100000 + 10;
class ITree {
  struct ITreeNode {
    int tot;
    long long sum, aim;
    ITreeNode() : tot(0), sum(0), aim(0){};
  };
  ITreeNode data_[kMaxIntervals];
  const int (&reference_)[kMaxPointsNum];
  int root_left_, root_right_;
  void Insert(int pos, int left, int right, int cursor);
  void Remove(int pos, int left, int right, int cursor);
  ITreeNode Query(int qleft, int qright, int left, int right, int cursor);

 public:
  ITree(const int (&refer)[kMaxPointsNum]) : reference_(refer) {
    root_left_ = 0;
    root_right_ = kMaxPointsNum;
  }
  void Insert(int pos);
  void Remove(int pos);
  long long Query(int qleft, int qright);
};
void ITree::Insert(int pos, int left, int right, int cursor) {
  ITreeNode &current = data_[cursor];
  ++current.tot;
  current.sum += reference_[pos];
  if (left + 1 < right) {
    int mid = (left + right) / 2;
    if (pos < mid)
      Insert(pos, left, mid, cursor * 2);
    else
      Insert(pos, mid, right, cursor * 2 + 1);
    ITreeNode &lc = data_[cursor * 2], &rc = data_[cursor * 2 + 1];
    current.aim = lc.aim + rc.aim + rc.sum * lc.tot - lc.sum * rc.tot;
  }
}
void ITree::Remove(int pos, int left, int right, int cursor) {
  ITreeNode &current = data_[cursor];
  --current.tot;
  current.sum -= reference_[pos];
  if (left + 1 < right) {
    int mid = (left + right) / 2;
    if (pos < mid)
      Remove(pos, left, mid, cursor * 2);
    else
      Remove(pos, mid, right, cursor * 2 + 1);
    ITreeNode &lc = data_[cursor * 2], &rc = data_[cursor * 2 + 1];
    current.aim = lc.aim + rc.aim + rc.sum * lc.tot - lc.sum * rc.tot;
  }
}
ITree::ITreeNode ITree::Query(int qleft, int qright, int left, int right,
                              int cursor) {
  if (qleft <= left && right <= qright) return data_[cursor];
  int mid = (left + right) / 2;
  ITreeNode ln, rn, ret;
  if (qleft < mid) ln = Query(qleft, qright, left, mid, cursor * 2);
  if (qright > mid) rn = Query(qleft, qright, mid, right, cursor * 2 + 1);
  ret.tot = ln.tot + rn.tot;
  ret.sum = ln.sum + rn.sum;
  ret.aim = ln.aim + rn.aim + rn.sum * ln.tot - ln.sum * rn.tot;
  return ret;
}
void ITree::Insert(int pos) { Insert(pos, root_left_, root_right_, 1); }
void ITree::Remove(int pos) { Remove(pos, root_left_, root_right_, 1); }
long long ITree::Query(int qleft, int qright) {
  ITreeNode result = Query(qleft, qright, root_left_, root_right_, 1);
  return result.aim;
}
int n;
int curr_pos[kMaxPointsNum];
int initial_pos[kMaxPointsNum];
int m;
int operations[kMaxOperations][3];
void Read() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%d", initial_pos + i);
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < 3; ++j) scanf("%d", &operations[i][j]);
  }
}
int size = 0;
int slots[kMaxPointsNum];
void Initialize() {
  int i, p, d;
  memmove(curr_pos, initial_pos, sizeof(curr_pos[0]) * n);
  for (i = 0; i < n; ++i) slots[size++] = curr_pos[i];
  for (i = 0; i < m; ++i) {
    if (operations[i][0] == 1) {
      p = --operations[i][1];
      d = operations[i][2];
      curr_pos[p] += d;
      slots[size++] = curr_pos[p];
    }
  }
  std::sort(slots, slots + size);
  size = std::unique(slots, slots + size) - slots;
}
void Run() {
  int i, px, delta, ql, qr;
  ITree *tree = new ITree(slots);
  for (i = 0; i < n; ++i) {
    curr_pos[i] = std::lower_bound(slots, slots + size, initial_pos[i]) - slots;
    tree->Insert(curr_pos[i]);
  }
  for (i = 0; i < m; ++i) {
    if (operations[i][0] == 1) {
      px = operations[i][1];
      delta = operations[i][2];
      tree->Remove(curr_pos[px]);
      curr_pos[px] =
          std::lower_bound(slots, slots + size, slots[curr_pos[px]] + delta) -
          slots;
      tree->Insert(curr_pos[px]);
    } else {
      ql = std::lower_bound(slots, slots + size, operations[i][1]) - slots;
      qr = std::upper_bound(slots, slots + size, operations[i][2]) - slots;
      printf("%I64d\n", tree->Query(ql, qr));
    }
  }
  delete tree;
}
int main() {
  Read();
  Initialize();
  Run();
}
