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 E {

	BufferedReader br;
	PrintWriter out;
	StringTokenizer st;
	boolean eof;

	static final Random rng = new Random();

	static class Node {
		Node l, r;
		int value;
		int size;

		long sum, sumDiff;

		static int getSize(Node v) {
			return v == null ? 0 : v.size;
		}

		static long getSum(Node v) {
			return v == null ? 0 : v.sum;
		}

		static long getSumDiff(Node v) {
			return v == null ? 0 : v.sumDiff;
		}

		Node makeInfo() {
			size = 1 + getSize(l) + getSize(r);
			sum = value + getSum(l) + getSum(r);
			sumDiff = getSumDiff(l) + getSumDiff(r) - getSum(l)
					* (1 + getSize(r)) + getSum(r) * (1 + getSize(l))
					+ (long) value * (getSize(l) - getSize(r));
			return this;
		}
		
		@Override
		public String toString() {
			String ret = "";
			if (l != null)
				ret += "(" + l.toString() + ") ";
			ret += value + ", " + size + ", " + sum + ", " + sumDiff;
			if (r != null)
				ret += " (" + r.toString() + ")";
			return ret;
		}

		static Node merge(Node left, Node right) {
			if (left == null)
				return right;
			if (right == null)
				return left;
			Node res;
			if (rng.nextInt(getSize(left) + getSize(right)) < getSize(left)) {
				res = left;
				res.r = merge(left.r, right);
			} else {
				res = right;
				res.l = merge(left, right.l);
			}
			return res.makeInfo();
		}

		static Node[] split(Node v, int mid) {
			if (v == null)
				return new Node[2];
			Node[] res;
			if (v.value <= mid) {
				res = split(v.r, mid);
				v.r = res[0];
				res[0] = v;
			} else {
				res = split(v.l, mid);
				v.l = res[1];
				res[1] = v;
			}
			v.makeInfo();
			return res;
		}

		static Node erase(Node v, int val) {
			if (v == null)
				return null;
			if (v.value == val) {
				return merge(v.l, v.r);
			}
			if (v.value < val) {
				v.r = erase(v.r, val);
			} else {
				v.l = erase(v.l, val);
			}
			return v.makeInfo();
		}

		public Node(int value, Node l, Node r) {
			this.value = value;
			this.l = l;
			this.r = r;
			this.makeInfo();
		}

		static Node insert(Node v, int val) {
			if (rng.nextInt(1 + getSize(v)) == 0) {
				Node[] tmp = split(v, val);
				return new Node(val, tmp[0], tmp[1]);
			}
			if (v.value <= val)
				v.r = insert(v.r, val);
			else
				v.l = insert(v.l, val);
			return v.makeInfo();
		}
	}

	void solve() throws IOException {
		int n = nextInt();
		int[] x = new int[n];

		Node root = null;

		for (int i = 0; i < n; i++) {
			x[i] = nextInt();
			root = Node.insert(root, x[i]);
		}
		
//		System.err.println(root);

		int q = nextInt();
		while (q-- > 0) {
			int type = nextInt();
			if (type == 1) {
				int i = nextInt() - 1;
				int delta = nextInt();
				root = Node.erase(root, x[i]);
				x[i] += delta;
				root = Node.insert(root, x[i]);
			} else {
				int low = nextInt();
				int high = nextInt();
				Node[] tmp0 = Node.split(root, low - 1);
				Node[] tmp1 = Node.split(tmp0[1], high);
				out.println(Node.getSumDiff(tmp1[0]));
//				System.err.println(tmp1[0]);
				root = Node.merge(tmp0[0], Node.merge(tmp1[0], tmp1[1]));
			}
		}
	}

	E() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	public static void main(String[] args) throws IOException {
		new E();
	}

	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				eof = true;
				return null;
			}
		}
		return st.nextToken();
	}

	String nextString() {
		try {
			return br.readLine();
		} catch (IOException e) {
			eof = true;
			return null;
		}
	}

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

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

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