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;
constexpr long long inf = 1e9 + 7, base = 541;
constexpr long long mod = 1e9 + 7, N = 1e6 + 7;
struct piii {
  long long sm = 0, an = 0, cn = 0;
};
long long n;
long long v[N];
long long sum[4 * N], ans[4 * N];
piii calc(piii x, piii y) {
  x.an += y.an + (y.sm * x.cn - x.sm * y.cn);
  x.sm += y.sm;
  x.cn += y.cn;
  return x;
}
inline long long pos(long long l, long long tp) {
  if (tp == 0)
    return (lower_bound(v, v + n + 1, l) - v);
  else
    return (upper_bound(v, v + n + 1, l) - v);
}
void build(long long s = 0, long long e = n, long long tag = 1) {
  if (e - s == 1) {
    sum[tag] = v[s];
    return;
  }
  long long mid = (s + e) / 2;
  build(s, mid, tag * 2 + 0);
  build(mid, e, tag * 2 + 1);
  sum[tag] = sum[tag * 2] + sum[tag * 2 + 1];
  ans[tag] = ans[tag * 2] + ans[tag * 2 + 1] +
             (sum[tag * 2 + 1] * (mid - s) - sum[tag * 2] * (e - mid));
}
piii query(long long l, long long r, long long tag = 1, long long s = 0,
           long long e = n) {
  piii x, y;
  if (s >= r || e <= l) return x;
  if (s >= l && e <= r) {
    x.sm = sum[tag], x.cn = e - s, x.an = ans[tag];
    return x;
  }
  long long mid = (s + e) / 2;
  x = query(l, r, tag * 2 + 0, s, mid), y = query(l, r, tag * 2 + 1, mid, e);
  return calc(x, y);
}
void builq(long long l, long long r, long long tag = 1, long long s = 0,
           long long e = n) {
  if (s >= r || e <= l) return;
  if (s >= l && e <= r) {
    build(s, e, tag);
    return;
  }
  long long mid = (s + e) / 2;
  builq(l, r, tag * 2 + 0, s, mid), builq(l, r, tag * 2 + 1, mid, e);
  sum[tag] = sum[tag * 2] + sum[tag * 2 + 1];
  ans[tag] = ans[tag * 2] + ans[tag * 2 + 1] +
             (sum[tag * 2 + 1] * (mid - s) - sum[tag * 2] * (e - mid));
}
long long a[N];
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
    v[i] = a[i];
  }
  sort(v, v + n);
  build(0, n, 1);
  long long Q;
  cin >> Q;
  for (long long i = n; i < n + 100; i++) v[i] = 1e18 + 7;
  while (Q--) {
    long long type, l, r;
    cin >> type >> l >> r;
    if (type == 2)
      cout << query(pos(l, 0), pos(r, 1)).an << endl;
    else {
      l--;
      long long x = (0 < pos(a[l], 0) ? pos(a[l], 0) : 0),
                y = (n - 1 > pos(a[l] + r, 0) ? pos(a[l] + r, 0) : n - 1);
      long long ps = x;
      v[x] += r, a[l] += r;
      while (v[ps] > v[ps + 1]) swap(v[ps], v[ps + 1]), ps++;
      while (ps && v[ps] < v[ps - 1]) swap(v[ps], v[ps - 1]), ps--;
      builq((x > y ? y : x), (x < y ? y : x) + 1);
    }
  }
}
