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 MAXN = 100000 + 10;
int n, m;
int arr[MAXN];
class Nod {
 public:
  Nod *l, *r;
  int lpos, rpos, mid, num;
  long long ans, sum;
  Nod(int lpos = 0, int rpos = 0, long long ans = 0, long long sum = 0,
      int num = 0) {
    this->lpos = lpos;
    this->rpos = rpos;
    mid = (lpos + rpos) / 2;
    this->ans = ans;
    this->sum = sum;
    this->num = num;
    l = r = NULL;
  }
  void buildChild() {
    if (l == NULL) l = new Nod(lpos, mid);
    if (r == NULL) r = new Nod(mid, rpos);
  }
  void update(Nod* a, Nod* l, Nod* r) {
    a->num = l->num + r->num;
    a->sum = l->sum + r->sum;
    a->ans = l->ans + r->ans + r->sum * l->num - r->num * l->sum;
  }
  void change(int x, bool b) {
    if (b) buildChild();
    if (rpos - lpos == 1) {
      num = b;
      sum = x * b;
      if (ans)
        cerr << "\"khanj\""
             << "= "
             << "khanj" << endl;
      return;
    }
    if (x < mid)
      l->change(x, b);
    else
      r->change(x, b);
    update(this, l, r);
  }
  Nod* get(int ll, int rr) {
    if (lpos >= rr || rpos <= ll || l == NULL) return new Nod();
    if (lpos >= ll && rpos <= rr) return new Nod(0, 0, ans, sum, num);
    Nod* ansl = l->get(ll, rr);
    Nod* ansr = r->get(ll, rr);
    Nod* ret = new Nod();
    update(ret, ansl, ansr);
    delete (ansl), delete (ansr);
    return ret;
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  Nod root(-1000000010, 1000000010);
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    root.change(arr[i], 1);
  }
  cin >> m;
  for (long long c, u, v, i = 0; i < m; i++) {
    cin >> c >> u >> v;
    if (c == 1) {
      int oldu = arr[u - 1];
      arr[u - 1] += v;
      root.change(oldu, 0);
      root.change(v + oldu, 1);
    }
    if (c == 2) {
      Nod* ans = root.get(u, v + 1);
      cout << ans->ans << '\n';
      delete (ans);
    }
  }
}
