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 long long N = 2e5 + 100;
struct segment {
  long long l, r, cnt, disL, disR, ans;
};
segment tree[4 * N];
vector<pair<long long, pair<long long, long long> > > query;
vector<long long> vec;
long long a[N], tmp[N];
long long n, m, sz;
inline long long id(long long x) {
  return lower_bound(vec.begin(), vec.end(), x) - vec.begin();
}
inline long long ID(long long x) {
  return upper_bound(vec.begin(), vec.end(), x) - vec.begin();
}
inline void make(long long i, long long l, long long r, long long cnt,
                 long long disL, long long disR, long long ans) {
  tree[i].l = l;
  tree[i].r = r;
  tree[i].cnt = cnt;
  tree[i].disL = disL;
  tree[i].disR = disR;
  tree[i].ans = ans;
}
inline segment makeNull(long long l, long long r) {
  segment null;
  null.l = l;
  null.r = r;
  null.cnt = null.disL = null.disR = null.ans = 0;
  return null;
}
inline segment merge(segment a, segment b) {
  segment res;
  res.l = a.l;
  res.r = b.r;
  res.cnt = a.cnt + b.cnt;
  res.disL = a.disL + b.cnt * (vec[a.r] - vec[a.l]) + b.disL;
  res.disR = b.disR + a.cnt * abs(vec[b.r] - vec[b.l]) + a.disR;
  res.ans = a.ans + b.ans + abs(a.cnt * b.disL) + (b.cnt * a.disR);
  return res;
}
void build(long long i = 1, long long L = 0, long long R = sz) {
  make(i, L, R, 0, 0, 0, 0);
  if (R - L == 1) return;
  long long m = (L + R) / 2;
  build(2 * i, L, m);
  build(2 * i + 1, m, R);
}
void insert(long long ind, long long i = 1, long long L = 0, long long R = sz) {
  if (R - L == 1) {
    make(i, L, R, 1, 0, (R == sz ? 0 : vec[R] - vec[L]), 0);
    return;
  }
  long long m = (L + R) / 2;
  if (ind < m)
    insert(ind, 2 * i, L, m);
  else
    insert(ind, 2 * i + 1, m, R);
  tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
void remove(long long ind, long long i = 1, long long L = 0, long long R = sz) {
  if (R - L == 1) {
    make(i, L, R, 0, 0, 0, 0);
    return;
  }
  long long m = (L + R) / 2;
  if (ind < m)
    remove(ind, 2 * i, L, m);
  else
    remove(ind, 2 * i + 1, m, R);
  tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
segment get(long long l, long long r, long long i = 1, long long L = 0,
            long long R = sz) {
  if (r <= L || R <= l) return makeNull(L, R);
  if (l <= L && R <= r) return tree[i];
  long long m = (L + R) / 2;
  return merge(get(l, r, 2 * i, L, m), get(l, r, 2 * i + 1, m, R));
}
int32_t main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
    tmp[i] = a[i];
    vec.push_back(a[i]);
  }
  cin >> m;
  for (long long i = 0; i < m; i++) {
    long long t, l, r, p, d;
    cin >> t;
    if (t == 1) {
      cin >> p >> d;
      tmp[--p] += d;
      vec.push_back(tmp[p]);
      query.push_back(pair<long long, pair<long long, long long> >(t, {p, d}));
    } else {
      cin >> l >> r;
      query.push_back(pair<long long, pair<long long, long long> >(t, {l, r}));
    }
  }
  sort(vec.begin(), vec.end());
  vector<long long>::iterator it = unique(vec.begin(), vec.end());
  vec.resize(distance(vec.begin(), it));
  sz = vec.size();
  build();
  for (long long i = 0; i < n; i++) insert(id(a[i]));
  for (auto [t, q] : query) {
    if (t == 1) {
      auto [p, d] = q;
      remove(id(a[p]));
      a[p] += d;
      insert(id(a[p]));
    } else {
      auto [l, r] = q;
      segment res;
      res = get(id(l), ID(r));
      cout << res.ans << '\n';
    }
  }
}
