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>
#pragma comment(linker, "/STACK:60000000")
using namespace std;
const long double eps = 1e-9;
const int inf = (1 << 30) - 1;
const long long inf64 = ((long long)1 << 62) - 1;
const long double pi = 3.1415926535897932384626433832795;
template <class T>
T sqr(T x) {
  return x * x;
}
map<int, int> num;
int n, m;
set<int> X;
map<int, int> mx;
int x[100500];
int x1[100500];
int tp[100500], c1[100500], c2[100500];
int tt[800500];
long long tsum[800500];
long long sum[800500];
long long tpush[800500];
int lst;
int xx[200500];
void ttupdate(int v, int value) {
  v = v + lst;
  tt[v] = value;
  while (v > 1) {
    v >>= 1;
    tt[v] = tt[v * 2] + tt[v * 2 + 1];
  }
}
void tsumupdate(int v, long long value, long long vvalue) {
  v = v + lst;
  long long add = value - tsum[v];
  tsum[v] = value;
  sum[v] = vvalue;
  while (v > 1) {
    v >>= 1;
    sum[v] = sum[v * 2] + sum[v * 2 + 1];
    tsum[v] += add;
  }
}
void push(int v) {
  tsum[v] += tpush[v] * sum[v];
  if (v < lst) {
    tpush[v * 2] += tpush[v];
    tpush[v * 2 + 1] += tpush[v];
  }
  tpush[v] = 0;
}
void tsumadd(int v, int l, int r, int a, int b, long long cnt) {
  push(v);
  if (r < a || l > b) return;
  if (a <= l && r <= b) {
    tpush[v] += cnt;
    return;
  }
  int mid = (l + r) / 2;
  tsumadd(v * 2, l, mid, a, b, cnt);
  tsumadd(v * 2 + 1, mid + 1, r, a, b, cnt);
  tsum[v] = tsum[v * 2] + tsum[v * 2 + 1];
}
int ttget(int v, int l, int r, int a, int b) {
  if (r < a || l > b) return 0;
  if (a <= l && r <= b) return tt[v];
  int mid = (l + r) / 2;
  return ttget(v * 2, l, mid, a, b) + ttget(v * 2 + 1, mid + 1, r, a, b);
}
void add(int x) {
  int pos = mx[x];
  tsumadd(1, 0, lst - 1, pos + 1, lst - 1, 1);
  ttupdate(pos, 1);
  int ind = ttget(1, 0, lst - 1, 0, pos);
  tsumadd(1, 0, lst - 1, pos, pos, 0);
  tsumupdate(pos, 2LL * x * (long long)ind, 2LL * x);
}
void del(int x) {
  int pos = mx[x];
  tsumadd(1, 0, lst - 1, pos + 1, lst - 1, -1);
  ttupdate(pos, 0);
  tsumadd(1, 0, lst - 1, pos, pos, 0);
  tsumupdate(pos, 0, 0);
}
pair<long long, long long> get_sum_ts(int v, int l, int r, int a, int b) {
  push(v);
  if (r < a || l > b) return make_pair(0LL, 0LL);
  if (a <= l && r <= b) return make_pair(tsum[v], sum[v]);
  int mid = (l + r) / 2;
  pair<long long, long long> p1, p2;
  p1 = get_sum_ts(v * 2, l, mid, a, b);
  p2 = get_sum_ts(v * 2 + 1, mid + 1, r, a, b);
  tsum[v] = tsum[v * 2] + tsum[v * 2 + 1];
  return make_pair(p1.first + p2.first, p1.second + p2.second);
}
long long get(int l, int r) {
  set<int>::iterator il = X.lower_bound(l);
  set<int>::iterator ir = X.lower_bound(r + 1);
  if (il == X.end()) return 0;
  if (ir == X.begin()) return 0;
  ir--;
  int pl = mx[*il];
  int pr = mx[*ir];
  if (pl > pr) return 0;
  pair<long long, long long> res = get_sum_ts(1, 0, lst - 1, pl, pr);
  pl = ttget(1, 0, lst - 1, 0, pl - 1) + 1;
  pr = ttget(1, 0, lst - 1, 0, pr);
  return res.first - res.second / 2 * (pr + pl);
}
int main() {
  cin >> n;
  for (int i = 0; i < (int)(n); i++) scanf("%d", &x[i]);
  cin >> m;
  for (int i = 0; i < (int)(n); i++) x1[i] = x[i];
  X.clear();
  for (int i = 0; i < (int)(n); i++) X.insert(x1[i]);
  for (int i = 0; i < (int)(m); i++) {
    scanf("%d%d%d", &tp[i], &c1[i], &c2[i]);
    if (tp[i] == 1) {
      c1[i]--;
      x1[c1[i]] += c2[i];
      X.insert(x1[c1[i]]);
    }
  }
  int pos = 0;
  for (set<int>::iterator it = X.begin(); it != X.end(); it++) {
    mx[*it] = pos;
    xx[pos] = *it;
    pos++;
  }
  memset(tt, 0, sizeof(tt));
  memset(sum, 0, sizeof(sum));
  memset(tsum, 0, sizeof(tsum));
  lst = 1;
  while (lst < (int)X.size() + 1) lst *= 2;
  for (int i = 0; i < (int)(n); i++) add(x[i]);
  for (int i = 0; i < (int)(m); i++) {
    if (tp[i] == 1) {
      int v = c1[i];
      del(x[v]);
      x[v] += c2[i];
      add(x[v]);
    } else {
      int l = c1[i];
      int r = c2[i];
      printf("%I64d\n", get(l, r));
    }
  }
  return 0;
}
