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;
template <typename T, typename U>
inline void smin(T &a, const U &b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, const U &b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T1, class T2>
inline void gn(T1 &x1, T2 &x2) {
  gn(x1), gn(x2);
}
template <class T1, class T2, class T3>
inline void gn(T1 &x1, T2 &x2, T3 &x3) {
  gn(x1, x2), gn(x3);
}
template <class T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <class T>
inline void println(T first) {
  print(first);
  putchar('\n');
}
template <class T>
inline void printsp(T first) {
  print(first);
  putchar(' ');
}
template <class T1, class T2>
inline void print(T1 x1, T2 x2) {
  printsp(x1), println(x2);
}
template <class T1, class T2, class T3>
inline void print(T1 x1, T2 x2, T3 x3) {
  printsp(x1), printsp(x2), println(x3);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = (long long)a * a % m)
    if (b & 1) ans = (long long)ans * a % m;
  return ans;
}
long long first[100010], second[100010];
long long arr[100010 << 2];
int nn;
pair<int, pair<int, int> > p[100010];
long long sum[(100010 << 4)], ans[(100010 << 4)];
int num[(100010 << 4)];
void push_up(int u) {
  num[u] = num[(u << 1)] + num[((u << 1) | 1)];
  sum[u] = sum[(u << 1)] + sum[((u << 1) | 1)];
  ans[u] = ans[(u << 1)] + ans[((u << 1) | 1)];
  ans[u] +=
      num[(u << 1)] * sum[((u << 1) | 1)] - num[((u << 1) | 1)] * sum[(u << 1)];
}
void update(int u, int L, int R, int l, int r, long long first, int k) {
  if (L >= r || R <= l) return;
  if (L >= l && R <= r) {
    sum[u] = first;
    num[u] = k;
    return;
  }
  update((u << 1), L, (L + R >> 1), l, r, first, k);
  update(((u << 1) | 1), (L + R >> 1), R, l, r, first, k);
  push_up(u);
}
int cnt;
long long s, sz;
void calc(int u, int L, int R, int l, int r) {
  if (L >= r || R <= l) return;
  if (L >= l && R <= r) {
    s += ans[u] + cnt * sum[u] - num[u] * sz;
    sz += sum[u];
    cnt += num[u];
    return;
  }
  calc((u << 1), L, (L + R >> 1), l, r);
  calc(((u << 1) | 1), (L + R >> 1), R, l, r);
}
int main() {
  int n, m;
  gn(n);
  for (int i = 1; i <= n; i++) {
    gn(first[i]);
    second[i] = first[i];
    arr[nn++] = first[i];
  }
  gn(m);
  for (int i = 0; i < m; i++) {
    gn(p[i].first, p[i].second.first, p[i].second.second);
    int a = p[i].second.first, b = p[i].second.second;
    if (p[i].first == 1) {
      second[a] += b;
      arr[nn++] = second[a];
    } else {
      arr[nn++] = a;
      arr[nn++] = b;
    }
  }
  sort(arr, arr + nn);
  nn = unique(arr, arr + nn) - arr;
  for (int i = 1; i <= n; i++) {
    int id = lower_bound(arr, arr + nn, first[i]) - arr;
    update(1, 0, nn, id, id + 1, first[i], 1);
  }
  for (int i = 0; i < m; i++) {
    int a = p[i].second.first, b = p[i].second.second;
    if (p[i].first == 1) {
      int id = lower_bound(arr, arr + nn, first[a]) - arr;
      update(1, 0, nn, id, id + 1, 0, 0);
      first[a] += b;
      id = lower_bound(arr, arr + nn, first[a]) - arr;
      update(1, 0, nn, id, id + 1, first[a], 1);
    } else {
      int l = lower_bound(arr, arr + nn, a) - arr;
      int r = upper_bound(arr, arr + nn, b) - arr;
      s = sz = cnt = 0;
      calc(1, 0, nn, l, r);
      println(s);
    }
  }
}
