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
import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws IOException {
    int n = nextInt();
    int []p = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = nextInt();
    }
    Treap a = null;
    for (int i = 0; i < n; ++i) {
      a = Treap.add(a, p[i]);
    }
    int m = nextInt();
    for (int i = 0; i < m; ++i) {
      int t = nextInt();
      if (t == 1) {
        int pos = nextInt() - 1;
        int d = nextInt();
        int x = p[pos];
        int y = x + d;
        p[pos] = y;
        a = Treap.add(Treap.remove(a, x), y);
      } else {
        int l = nextInt();
        int r = nextInt();
        Treap s = Treap.split(Treap.split(a, l).R, r + 1).L;
        long res = Treap.data(s).pairSum;
        System.out.println(res);
      }
    }
  }
  
  static class Treap {
    int x, w;
    Treap L, R;
    
    static class Data {
      public long size, sum, pairSum;
      public Data(long size, long sum, long pairSum) {
        this.size = size;
        this.sum = sum;
        this.pairSum = pairSum;
      }
    }
    Data data;
    
    public Treap(int x, int w, Treap L, Treap R) {
      this.x = x;
      this.w = w;
      this.L = L;
      this.R = R;
      this.data = null;
    }

    public static Treap remove(Treap t, int x) {
      Pair p = split(t, x);
      Pair q = split(p.R, x + 1);
      return merge(p.L, q.R);
    }

    public static Data data(Treap t) {
      if (t == null) {
        return new Data(0, 0, 0);
      }
      if (t.data == null) {
        Data dataL = data(t.L);
        Data dataR = data(t.R);
        t.data = new Data(
            dataL.size + 1 + dataR.size,
            dataL.sum + t.x + dataR.sum,
            dataL.pairSum + dataR.pairSum + (dataR.sum * dataL.size - dataL.sum * dataR.size) + 
                dataL.size * t.x - dataL.sum + dataR.sum - dataR.size * t.x);
      }
      return t.data;
    }

    static class Pair {
      public Treap L, R;
      public Pair(Treap L, Treap R) {
        this.L = L;
        this.R = R;
      }
    }
    
    static Pair split(Treap t, int x) {
      if (t == null) return new Pair(null, null);
      Pair p;
      if (x <= t.x) {
        p = split(t.L, x);
        p.R = new Treap(t.x, t.w, p.R, t.R);
      } else {
        p = split(t.R, x);
        p.L = new Treap(t.x, t.w, t.L, p.L);
      }
      return p;
    }
    
    static Random r = new Random();
    public static Treap add(Treap t, int x) {
      Treap e = new Treap(x, r.nextInt(), null, null);
      if (t == null) return e;
      Pair p = split(t, x);
      return merge(merge(p.L, e), p.R);
    }

    private static Treap merge(Treap L, Treap R) {
      if (L == null) return R;
      if (R == null) return L;
      if (L.w < R.w) {
        return new Treap(R.x, R.w, merge(L, R.L), R.R);
      } else {
        return new Treap(L.x, L.w, L.L, merge(L.R, R));
      }
    }
  }
  
  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static StringTokenizer st;

  static String nextToken() throws IOException {
      while (st == null || !st.hasMoreTokens()) {
          String line = br.readLine();
          if (line == null) {
              return null;
          }
          st = new StringTokenizer(line);
      }
      return st.nextToken();
  }

  static int nextInt() throws IOException {
      return Integer.parseInt(nextToken());
  }

  static long nextLong() throws IOException {
      return Long.parseLong(nextToken());
  }

  static double nextDouble() throws IOException {
      return Double.parseDouble(nextToken());
  }
}
