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;
struct q_ {
  int t;
  int a;
  int b;
};
struct node_ {
  int x;
  node_ *l, *r;
  int ex;
  int min, max;
  int n;
  long long s, v;
};
void parse(node_ *t, int onlyex = 0) {
  if (t == NULL) return;
  parse(t->l, onlyex);
  if (!onlyex || t->ex) {
    cout << "x " << t->x << endl;
    cout << "ex " << t->ex << endl;
    cout << "min " << t->min << endl;
    cout << "max " << t->max << endl;
    cout << "n " << t->n << endl;
    cout << "s " << t->s << endl;
    cout << "v " << t->v << endl;
    cout << endl;
  }
  parse(t->r, onlyex);
}
void parse2(node_ *t, int level = 1) {
  if (t == NULL) return;
  parse2(t->l, level + 1);
  cout << "x " << t->x << endl;
  cout << "ex " << t->ex << endl;
  cout << "level " << level << endl;
  cout << endl;
  parse2(t->r, level + 1);
}
vector<int> v;
int x[100000];
int x_[100000];
int n, m, vs;
q_ q[100000];
node_ *t;
node_ pool[200004];
int poolsz;
void mix(int n1, long long s1, long long v1, int n2, long long s2, long long v2,
         int &n, long long &s, long long &v) {
  v = v1 + v2 + n1 * s2 - n2 * s1;
  n = n1 + n2;
  s = s1 + s2;
}
node_ *maketree(int i, int j) {
  if (i > j) return NULL;
  int m = (i + j) / 2;
  node_ *n = &pool[poolsz++];
  n->x = v[m];
  n->ex = 0;
  n->l = maketree(i, m - 1);
  n->r = maketree(m + 1, j);
  return n;
}
void mark(int x, node_ *t) {
  if (t->x == x)
    t->ex = 1;
  else if (x < t->x)
    mark(x, t->l);
  else
    mark(x, t->r);
}
void setup(node_ *t, int &n, long long &s, long long &v, int &min, int &max) {
  if (t == NULL) {
    min = 2000000000;
    max = -2000000000;
    n = 0;
    s = 0;
    v = 0;
  } else {
    int n1, mn1, mx1, n2, mn2, mx2;
    long long s1, v1, s2, v2;
    setup(t->l, n1, s1, v1, mn1, mx1);
    setup(t->r, n2, s2, v2, mn2, mx2);
    min = 2000000000;
    max = -2000000000;
    if (t->ex) {
      mix(n1, s1, v1, 1, t->x, 0, n1, s1, v1);
      min = t->x;
      max = t->x;
    }
    mix(n1, s1, v1, n2, s2, v2, n, s, v);
    min = (min < mn1 ? min : mn1);
    min = (min < mn2 ? min : mn2);
    max = (max > mx1 ? max : mx1);
    max = (max > mx2 ? max : mx2);
    t->n = n;
    t->s = s;
    t->v = v;
    t->min = min;
    t->max = max;
  }
}
void q2(node_ *t, int l, int r, int &n, long long &s, long long &v) {
  if (t == NULL || t->max < l || t->min > r) {
    n = 0;
    s = 0;
    v = 0;
  } else if (t->x < l) {
    q2(t->r, l, r, n, s, v);
  } else if (t->x > r) {
    q2(t->l, l, r, n, s, v);
  } else {
    if (l <= t->min && r >= t->max) {
      n = t->n;
      s = t->s;
      v = t->v;
      return;
    }
    int n1, n2;
    long long s1, v1, s2, v2;
    q2(t->l, l, r, n1, s1, v1);
    q2(t->r, l, r, n2, s2, v2);
    if (t->ex) {
      mix(n1, s1, v1, 1, t->x, 0, n1, s1, v1);
    }
    mix(n1, s1, v1, n2, s2, v2, n, s, v);
  }
}
void q1(node_ *t, int x, int add, int &n, long long &s, long long &v, int &min,
        int &max) {
  if (t == NULL) {
    n = 0;
    s = 0;
    v = 0;
    return;
  }
  int n1, mn1, mx1;
  int nm, mnm, mxm;
  int n2, mn2, mx2;
  long long s1, v1, sm, vm, s2, v2;
  if (x == t->x) {
    t->ex = add;
    n1 = (t->l == NULL ? 0 : t->l->n);
    s1 = (t->l == NULL ? 0 : t->l->s);
    v1 = (t->l == NULL ? 0 : t->l->v);
    mn1 = (t->l == NULL ? 2000000000 : t->l->min);
    mx1 = (t->l == NULL ? -2000000000 : t->l->max);
    nm = add;
    sm = (add ? t->x : 0);
    vm = 0;
    mnm = (add ? t->x : 2000000000);
    mxm = (add ? t->x : -2000000000);
    n2 = (t->r == NULL ? 0 : t->r->n);
    s2 = (t->r == NULL ? 0 : t->r->s);
    v2 = (t->r == NULL ? 0 : t->r->v);
    mn2 = (t->r == NULL ? 2000000000 : t->r->min);
    mx2 = (t->r == NULL ? -2000000000 : t->r->max);
  } else if (x < t->x) {
    q1(t->l, x, add, n1, s1, v1, mn1, mx1);
    nm = t->ex;
    sm = (t->ex ? t->x : 0);
    vm = 0;
    mnm = (t->ex ? t->x : 2000000000);
    mxm = (t->ex ? t->x : -2000000000);
    n2 = (t->r == NULL ? 0 : t->r->n);
    s2 = (t->r == NULL ? 0 : t->r->s);
    v2 = (t->r == NULL ? 0 : t->r->v);
    mn2 = (t->r == NULL ? 2000000000 : t->r->min);
    mx2 = (t->r == NULL ? -2000000000 : t->r->max);
  } else {
    n1 = (t->l == NULL ? 0 : t->l->n);
    s1 = (t->l == NULL ? 0 : t->l->s);
    v1 = (t->l == NULL ? 0 : t->l->v);
    mn1 = (t->l == NULL ? 2000000000 : t->l->min);
    mx1 = (t->l == NULL ? -2000000000 : t->l->max);
    nm = t->ex;
    sm = (t->ex ? t->x : 0);
    vm = 0;
    mnm = (t->ex ? t->x : 2000000000);
    mxm = (t->ex ? t->x : -2000000000);
    q1(t->r, x, add, n2, s2, v2, mn2, mx2);
  }
  min = (mn1 < mnm ? mn1 : mnm);
  min = (min < mn2 ? min : mn2);
  max = (mx1 > mxm ? mx1 : mxm);
  max = (max > mx2 ? max : mx2);
  mix(n1, s1, v1, nm, sm, vm, n1, s1, v1);
  mix(n1, s1, v1, n2, s2, v2, n, s, v);
  t->n = n;
  t->s = s;
  t->v = v;
  t->min = min;
  t->max = max;
}
int main() {
  ios_base::sync_with_stdio(false);
  poolsz = 0;
  cin >> n;
  v.reserve(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i];
    v.push_back(x[i]);
  }
  memcpy(x_, x, sizeof(int) * n);
  cin >> m;
  v.reserve(n + m);
  for (int i = 0; i < m; i++) {
    cin >> q[i].t >> q[i].a >> q[i].b;
    if (q[i].t == 1) {
      q[i].a--;
      x_[q[i].a] += q[i].b;
      v.push_back(x_[q[i].a]);
    }
  }
  sort(v.begin(), v.end());
  vs = 1;
  for (int i = 1; i < v.size(); i++) {
    if (v[i] != v[vs - 1]) v[vs++] = v[i];
  }
  t = maketree(0, vs - 1);
  for (int i = 0; i < n; i++) mark(x[i], t);
  int i1, i4, i5;
  long long l2, l3;
  setup(t, i1, l2, l3, i4, i5);
  for (int i = 0; i < m; i++) {
    if (q[i].t == 1) {
      q1(t, x[q[i].a], 0, i1, l2, l3, i4, i5);
      x[q[i].a] += q[i].b;
      q1(t, x[q[i].a], 1, i1, l2, l3, i4, i5);
    } else {
      q2(t, q[i].a, q[i].b, i1, l2, l3);
      cout << l3 << endl;
    }
  }
  return 0;
}
