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.*;
public class E295 {
	
	class InputReader {

		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public InputReader() throws FileNotFoundException {
			reader = new BufferedReader(new FileReader("d:/input.txt"));
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

	}
	
	public class query{
		int opt;
		long x , y;
		public query(int opt,long x ,long y){
			this.opt = opt;
			this.x = x ;
			this.y = y;
		}
	}
	
	public class node{
		
		int left,right;
		long key = 0;
		int size = 0;
		long sum = 0;
		public node(int left , int right){
			this.left = left;
			this.right = right;
		}
		public int mid(){
			return (left+right)/2;
		}
		
	}
	
	node tree[];
	public void build(int left ,int right, int idx){
		tree[idx] = new node(left,right);
		if(left == right)
			return;
		int mid = tree[idx].mid();
		build(left,mid,idx << 1);
		build(mid+1,right,idx << 1 | 1);
		pushup(idx);
	}
	
	public void pushup(int idx){
		tree[idx].size = tree[idx << 1].size + tree[idx << 1 | 1].size;
		tree[idx].key = tree[idx << 1].key + tree[idx << 1 | 1].key;
		tree[idx].sum = tree[idx << 1].sum + tree[idx << 1 | 1].sum 
				+ tree[idx << 1].size * tree[idx << 1 | 1].key - tree[idx << 1 |1].size * tree[idx << 1].key;
	}
	
	public void del(int pos , int idx){
		
		if(tree[idx].left == tree[idx].right){
			tree[idx].size = 0;
			tree[idx].key = 0;
			tree[idx].sum = 0;
			return;
		}
		int mid  = tree[idx].mid();
		if(pos <= mid) del(pos,idx << 1);
		else del(pos, idx << 1 | 1);
		pushup(idx);
	}
	
	public void insert(int pos, long val , int idx){
		if(tree[idx].left == tree[idx].right){
			tree[idx].size = 1;
			tree[idx].key = val;
			tree[idx].sum = 0;
			return;
		}
		int mid = tree[idx].mid();
		if(pos <= mid) insert(pos , val , idx << 1);
		else insert(pos,val,idx << 1 | 1);
		pushup(idx);
	}
	
	public node query(int left,int right,int idx){
		
		if(left == tree[idx].left && right == tree[idx].right){
			return tree[idx];
		}
		int mid = tree[idx].mid();
		if(right <= mid) return query(left,right,idx << 1);
		else if(left > mid) return query(left,right,idx << 1 | 1);
		else{
			node l = query(left,mid,idx << 1);
			node r = query(mid+1,right,idx << 1 |1);
			node ans = new node(left,right);
			ans.size = l.size + r.size;
			ans.key = l.key + r.key;
			ans.sum = l.sum + r.sum + l.size * r.key - r.size * l.key;
			return ans;
		}
		
	}
	
	public void run(){
		
		InputReader reader = new InputReader(System.in);
		TreeMap<Long,Integer> map = new TreeMap<Long,Integer>();
		int n = reader.nextInt();
		long a[] = new long[n+1];
		long b[] = new long[n+1];
		for(int i = 1 ; i <= n ; i ++){
			a[i] = reader.nextLong();
			b[i] = a[i];
			map.put(a[i], 0);
		}
		int m = reader.nextInt();
		query q[] = new query[m];
		for(int i = 0 ; i < m ; i ++){
			q[i] = new query(reader.nextInt(),reader.nextLong(),reader.nextLong());
//			System.out.println(q[i].opt+" "+ q[i].x + " " + q[i].y);
			if(q[i].opt == 1){
				b[(int)q[i].x] += q[i].y;
				map.put(b[(int)q[i].x], 0);
			}else{
				map.put(q[i].x, 0);
				map.put(q[i].y, 0);
			}
		}
		Set<Long> set = map.keySet();
		int cnt = 1;
		for(Long i : set){
			map.put(i, cnt ++);
		}
		tree = new node[cnt*4];
		build(1,cnt,1);
		for(int i = 1; i <= n ; i ++){
			insert(map.get(a[i]),a[i],1);
		}
		for(int i = 0 ; i < m ;i ++){
//			System.out.println(q[i].opt+" "+ q[i].x + " " + q[i].y);
			if(q[i].opt == 1){
				del(map.get(a[(int)q[i].x]),1);
				a[(int)q[i].x] += q[i].y;
				insert(map.get(a[(int)q[i].x]),a[(int)q[i].x],1);
			}else{
//				System.out.println(map.get(q[i].x)+" "+map.get(q[i].y));
				node ans = query(map.get(q[i].x),map.get(q[i].y),1);
				System.out.println(ans.sum);
			}
		}
		
	}
	
	public static void main(String[] args) {
		new E295().run();
	}

}
