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 GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.2")
using namespace std;
inline void opting() {
  ios_base::sync_with_stdio(false);
  cout.tie(0);
  cin.tie(0);
}
long long inp() {
  long long x;
  cin >> x;
  return x;
}
void make_unique(vector<long long> &vec, bool sorted = false) {
  if (!sorted) sort((vec).begin(), (vec).end());
  vec.resize(unique((vec).begin(), (vec).end()) - vec.begin());
}
void file_edit(bool reader = true, bool writer = false) {
  if (reader) freopen("Test_input.txt", "r", stdin);
  if (writer) freopen("Test_output.txt", "w", stdout);
}
const long long SQRT = 350 + 10, lg = 18 + 2, inlim = 2147483647;
const long long maxn = 4e5 + 69, delta = 998244353, inf = 1e9 + 420;
vector<long long> maper;
struct seg_data {
  long long cnt = 0, L = 0;
  long long sum = 0;
  long long l_dist, r_dist;
} seg[4 * maxn], null_data;
void show_data(seg_data &A) {
  cout << "cnt: " << A.cnt << '\n';
  cout << "length: " << A.L << '\n';
  cout << "sum: " << A.sum << '\n';
  cout << "l_dist & r_dist: " << A.l_dist << ' ' << A.r_dist << '\n';
}
void base_seting(seg_data &d) {
  d.sum = 0;
  d.l_dist = 0;
  d.cnt = 1 - d.cnt;
  d.r_dist = d.cnt * d.L;
}
void sag(seg_data &d, const seg_data &A, const seg_data &B,
         const long long &xt) {
  d.L = A.L + B.L;
  d.cnt = A.cnt + B.cnt;
  d.l_dist = A.l_dist + B.l_dist + (A.L * B.cnt);
  d.r_dist = B.r_dist + A.r_dist + (B.L * A.cnt);
  d.sum = A.sum + B.sum + A.cnt * B.l_dist + B.cnt * A.r_dist;
}
long long n, q;
bool FRD = false;
void update(const long long &idx, const long long &L = 0,
            const long long &R = n, const long long &id = 1) {
  seg[id].L = maper[R] - maper[L];
  if (R <= idx or idx < L) return;
  if (R - L == 1)
    base_seting(seg[id]);
  else {
    long long mid = (L + R) >> 1;
    update(idx, L, mid, id * 2);
    update(idx, mid, R, id * 2 + 1);
    sag(seg[id], seg[id * 2], seg[id * 2 + 1], maper[mid] - maper[mid - 1]);
  }
  if (FRD) {
    cout << "just set " << L << " to " << R << ":\n";
    show_data(seg[id]);
    cout << endl;
  }
  return;
}
seg_data get_dists(const long long &l, const long long &r,
                   const long long &L = 0, const long long &R = n,
                   const long long &id = 1) {
  seg[id].L = maper[R] - maper[L];
  if (r <= L or R <= l) return null_data;
  if (l <= L and R <= r) {
    return seg[id];
  }
  long long mid = (L + R) >> 1;
  seg_data A = get_dists(l, r, L, mid, id * 2);
  seg_data B = get_dists(l, r, mid, R, id * 2 + 1);
  seg_data C = null_data;
  sag(C, A, B, maper[mid] - maper[mid - 1]);
  return C;
}
struct query {
  bool type;
  long long F, S;
} q_tmp;
vector<query> Q;
vector<long long> initial;
long long find_maped(const long long &key) {
  return (lower_bound((maper).begin(), (maper).end(), key) - maper.begin());
}
vector<long long> SUCK;
void input() {
  n = inp();
  for (long long i = 0; i < n; i++) {
    initial.push_back(inp());
    maper.push_back(initial[i]);
    SUCK.push_back(initial[i]);
  }
  q = inp();
  for (long long i = 0; i < q; i++) {
    q_tmp.type = inp() - 1;
    q_tmp.F = inp();
    q_tmp.S = inp();
    if (!q_tmp.type) {
      long long id = q_tmp.F - 1;
      q_tmp.F = SUCK[id];
      q_tmp.S += q_tmp.F;
      SUCK[id] = q_tmp.S;
    }
    Q.push_back(q_tmp);
    maper.push_back(q_tmp.F);
    maper.push_back(q_tmp.S);
  }
  make_unique(maper);
  n = maper.size();
}
void predo() {
  null_data.cnt = null_data.L = null_data.l_dist = null_data.sum =
      null_data.r_dist = 0;
}
void solve() {
  for (auto A : initial) {
    update(find_maped(A));
  }
  for (auto quer : Q) {
    if (quer.type) {
      cout << get_dists(find_maped(quer.F), find_maped(quer.S) + 1).sum << '\n';
    } else {
      update(find_maped(quer.F));
      update(find_maped(quer.S));
    }
  }
}
int main() {
  opting();
  input();
  predo();
  solve();
}
