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 N = 100 * 1000 + 1;
int n, q;
long long arr[N];
pair<long long, long long> seg[4 * N];
int b[N];
inline pair<long long, long long> merge(pair<long long, long long> a,
                                        pair<long long, long long> b, int &s,
                                        int &mid, int &e) {
  return make_pair(
      a.first + b.first +
          ((e - mid) * (arr[mid] - arr[s]) + b.second) * (mid - s) -
          (e - mid) * a.second,
      (e - mid) * (arr[mid] - arr[s]) + a.second + b.second);
}
void build(int v, int s, int e) {
  if (e - s == 1) {
    seg[v] = make_pair(0, 0);
    return;
  }
  int mid = (s + e) / 2;
  build(2 * v + 0, s, mid);
  build(2 * v + 1, mid, e);
  seg[v] = merge(seg[2 * v + 0], seg[2 * v + 1], s, mid, e);
}
void update(int v, int s, int e, int p, int val) {
  if (p < s || p >= e) return;
  if (e - s == 1 && p == s) {
    arr[p] += val;
    return;
  }
  int mid = (s + e) / 2;
  update(2 * v + 0, s, mid, p, val);
  update(2 * v + 1, mid, e, p, val);
  seg[v] = merge(seg[2 * v + 0], seg[2 * v + 1], s, mid, e);
}
pair<long long, long long> get(int v, int s, int e, int l, int r) {
  if (l == s && e == r) return seg[v];
  if (e - s == 1) return seg[v];
  int mid = (s + e) / 2;
  if (mid >= r)
    return get(2 * v + 0, s, mid, l, r);
  else if (mid <= l)
    return get(2 * v + 1, mid, e, l, r);
  else
    return merge(get(2 * v + 0, s, mid, l, mid), get(2 * v + 1, mid, e, mid, r),
                 l, mid, r);
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%d", &b[i]), arr[i] = b[i];
  sort(arr, arr + n);
  build(1, 0, n);
  scanf("%d", &q);
  for (int i = 0; i < q; ++i) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int p, d;
      scanf("%d%d", &p, &d);
      p--;
      int tmp = b[p];
      b[p] += d;
      p = lower_bound(arr, arr + n, tmp) - arr;
      if (d >= 0) {
        for (int i = 0; i < d; ++i) {
          if (p == n - 1) {
            update(1, 0, n, p, d - i);
            break;
          }
          if (p != n - 1 && arr[p + 1] - arr[p] > 1) {
            int tmp = min(int(arr[p + 1] - arr[p]), d - i);
            update(1, 0, n, p, tmp);
            i += tmp - 1;
            continue;
          }
          if (!(p == n - 1 || arr[p] < arr[p + 1])) p++;
          update(1, 0, n, p, 1);
        }
      } else {
        for (int i = 0; i < -d; ++i) {
          if (p == 0) {
            update(1, 0, n, p, d + i);
            break;
          }
          if (p != 0 && arr[p] - arr[p - 1] > 1) {
            int tmp = min(int(arr[p] - arr[p - 1]), -d - i);
            update(1, 0, n, p, -tmp);
            i += tmp - 1;
            continue;
          }
          if (!(p == 0 || arr[p] > arr[p - 1])) p--;
          update(1, 0, n, p, -1);
        }
      }
    } else {
      int l, r;
      scanf("%d%d", &l, &r);
      l = lower_bound(arr, arr + n, l) - arr;
      r = upper_bound(arr, arr + n, r) - arr;
      if (l == r)
        printf("0\n");
      else
        printf("%I64d\n", get(1, 0, n, l, r).first);
    }
  }
  return 0;
}
