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

/*
  This is an implementation of a recursive splaying algorithm.
  It depends on "deep splay" to keep the tree balanced
  preventing stack overflow on the splays, and guaranteeing O(log n)
  worst case time.  It uses the snip/glue paradigm to easily incorporate 
  complicated augmentations.
*/

public class E {
    static class Node {
	Node l, r;
	long x;
	int size, depth;
	long sum, diff;

	Node(Node lx, Node rx, int sizex, int depthx, long xx, long sumx, long diffx) {
	    l = lx;
	    r = rx;
	    x = xx;
	    size = sizex;
	    depth = depthx;
	    sum = sumx;
	    diff = diffx;
	}
    }

    private static Node nullNode;
    static {
	nullNode = new Node(null, null, 0, 0, 0, 0, 0);
    }

    static Node connect(Node ll, Node k, Node rr) {
	k.l = ll;
	k.r = rr;
	return k;
    }

    static Node glue(Node ll, Node k, Node rr) {
	k.size = ll.size + 1 + rr.size;
	k.depth = 1 + Math.max(ll.depth, rr.depth);
	k.l = ll;
	k.r = rr;
	k.sum = ll.sum + k.x + rr.sum;
	k.diff = ll.diff + rr.diff + rr.sum*ll.size - ll.sum*rr.size 
	    + k.x*ll.size - ll.sum
	    + rr.sum - k.x*rr.size;
	return k;
    }

    static Node snip(Node n) {
	Node l=n.l,  r=n.r;
	n.size = n.depth = 1;
	n.sum = n.x;
	n.diff = 0;
	return n;
    }

    static Node splayRank(Node t, int rank) {
	/* t is already snipped.  returns a splayed tree, which is in the snipped state */
	if (rank == t.l.size) return t;
	if (rank < t.l.size) {
	    Node u = snip(t.l);
	    if (rank == u.l.size) return connect(u.l, u, glue(u.r, t, t.r));
	    if (rank < u.l.size) {
		Node v = snip(u.l);
		v = splayRank(v, rank);
		return connect(v.l, v, glue(v.r, u, glue(u.r, t, t.r)));
	    } else {
		u = splayRank(u, rank);
		return connect(u.l, u, glue(u.r, t, t.r));		
	    }
	} else {
	    rank -= t.l.size+1;
	    Node u = snip(t.r);
	    if (rank == u.l.size) return connect(glue(t.l, t, u.l), u, u.r);
	    if (rank > u.l.size) {
		Node v = snip(u.r);
		v = splayRank(v, rank - (u.l.size+1));
		return connect(glue(glue(t.l, t, u.l), u, v.l), v, v.r);
	    } else {
		u = splayRank(u, rank);
		return connect(glue(t.l, t, u.l), u, u.r);
	    }
	}
    }

    static Node splay(Node t, int rank) {
	if (t == nullNode) return t;
	t = splayRank(snip(t), rank);
	return glue (t.l, t, t.r);
    }

    static int rankOfKey(Node t, long x) {
	/* Return the rank of the node with this key, or, if this key
	   is not in the tree, returns the rank of the one after it. */
	if (t == nullNode) return 0;
	int sl = t.l.size;
	if (x == t.x) return sl;
	if (x < t.x) return rankOfKey(t.l, x);
	return sl + 1 + rankOfKey(t.r, x);
    }
    
    static int rankOfDeepest(Node t) {
	if (t.depth == 1) return 0;
	if (t.l.depth >= t.r.depth) return rankOfDeepest(t.l);
	return t.l.size + 1 + rankOfDeepest(t.r);
    }

    static Node deepSplay(Node t) {
	if (t == nullNode) return t;
	int i=0;
	while ((1 << i) < t.size) i++;
	if (t.depth <= 5*(i+1)) return t; /* improve the tree if its depth is more than 5 log n */
	return splay(t, rankOfDeepest(t));
    }

    static Node insert(Node t, long x) {
	int r = rankOfKey(t,x);
	Node n = new Node(nullNode, nullNode, 1, 1, x, x, 0);
	if (r == t.size) return glue(t,n,nullNode);
	t = snip(splay(t, r));
	Node tl = t.l;
	return glue(tl, n, glue(nullNode,t,t.r));
    }

    static Node join(Node a, Node b) {
	if (a==nullNode) return b;
	a = splay(a, a.size-1);
	snip(a);
	return glue(a.l, a, b);
    }

    static Node deleteRoot(Node t) {
	t = snip(t);
	return join(t.l, t.r);
    }

    static void split(Node t, long k, boolean putInLeft, Node[] ret) { 
	// if k is in the tree, putInLeft tells you to put it in the left part
	int r = rankOfKey(t,k);
	if (r == t.size) {
	    ret[0] = t;
	    ret[1] = nullNode;
	} else {
	    t = snip(splay(t,r)); // if k was in the tree, then it's the root
	    // we know that t.r.x >= k
	    if (putInLeft && t.x == k) {
		ret[1] = t.r;
		ret[0] = glue(t.l, t, nullNode);
	    } else {
		ret[0] = t.l;
		ret[1] = glue(nullNode, t, t.r);
	    }
	}
    }

    /*
    static void printTree(Node t, int d) {
	if (t == nullNode) return;
	printTree(t.r, d+1);
	for (int i=0; i<d; i++) System.out.printf("    ");
	System.out.printf("(%d, %d, %d) \n", t.x, t.size, t.depth);
	printTree(t.l, d+1);
    }
    */

    public void read_input_and_solve() throws IOException, MyException {
	StringBuilder out = new StringBuilder();

	Node[] spl1 = new Node[2];
	Node[] spl2 = new Node[2];
	long total = 0;
	Node t = nullNode;
	int n = nextInt();
	long xa[] = new long[n];

	for (int i=0; i<n; i++) {
	    xa[i] = nextInt();
	    t = insert(t,xa[i]);
	}

	int m = nextInt();

	for (int i=0; i<m; i++) {
	    if (nextInt() == 1) {
		int p = nextInt();
		int d = nextInt();
		long oldx = xa[p-1];
		xa[p-1] += d;
		t = splay(t, rankOfKey(t,oldx));
		t = deleteRoot(t);
		t = insert(t, xa[p-1]);
	    } else {
		long lx = nextLong();
		long rx = nextLong();
		split(t, lx, false, spl1);
		split(spl1[1], rx, true, spl2);
		out.append(String.format("%d\n", spl2[0].diff));
		t = join(spl1[0], join(spl2[0], spl2[1]));
	    }
	    t = deepSplay(t);
	}
	System.out.print(out);	    
    }

    public static void main(String[] args) {
	(new E()).run();
    }
    
    BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter writer;
    
    public void run() {
	try {
	    reader = new BufferedReader(new InputStreamReader(System.in));
	    tokenizer = null;
	    writer = new PrintWriter(System.out);
	    read_input_and_solve();
	    reader.close();
	    writer.close();
	} catch (Exception e) {
	    e.printStackTrace();
	    System.exit(1);
	}
    }
    
    int nextInt() throws IOException {
	return Integer.parseInt(nextToken());
    }
    
    long nextLong() throws IOException {
	return Long.parseLong(nextToken());
    }
    
    double nextDouble() throws IOException {
	return Double.parseDouble(nextToken());
    }
    
    String nextToken() throws IOException {
	while (tokenizer == null || !tokenizer.hasMoreTokens()) {
	    tokenizer = new StringTokenizer(reader.readLine());
	}
	return tokenizer.nextToken();
    }
}

class MyException extends Exception {
    public String s;
    public MyException(String prob) {
	super(prob);
	s = prob;
    }
}
