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.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.util.Set;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
import java.util.TreeSet;
import java.io.Writer;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author ogiekako
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		MyScanner in = new MyScanner(inputStream);
		MyPrintWriter out = new MyPrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    public void solve(int testNumber, MyScanner in, MyPrintWriter out) {
        int n = in.nextInt();
        int[] x = new int[n];
        Set<Integer> xSet = new TreeSet<Integer>();
        for (int i = 0; i < n; i++) {
            x[i] = in.nextInt();
            xSet.add(x[i]);
        }
        int m = in.nextInt();
        int[] t = new int[m], l = new int[m], r = new int[m];
        int[] tmp = x.clone();
        for (int i = 0; i < m; i++) {
            t[i] = in.nextInt(); l[i] = in.nextInt(); r[i] = in.nextInt();
            if (t[i] == 1) {
                l[i]--;
                tmp[l[i]] += r[i];
                xSet.add(tmp[l[i]]);
            }else{
                r[i]++;
                xSet.add(l[i]);
                xSet.add(r[i]);
            }
        }
        int[] sortX = tois(xSet.toArray(new Integer[xSet.size()]));
        Arrays.sort(sortX);
        SegTreeSemigroup<Entry> list = new SegTreeSemigroup<Entry>(sortX.length) {

            @Override
            protected Entry operate(Entry left, Entry right) {
                if (left == null) return right;
                if (right == null) return left;
                int nNum = left.num + right.num;
                long nSum = left.sum + right.sum;
                long nProd = left.prod + right.prod +
                        (right.sum * left.num - left.sum * right.num);
                return new Entry(nNum, nSum, nProd);
            }

            @Override
            protected Entry identity() {
                return new Entry(0, 0, 0);
            }
        };
        for (int i = 0; i < n; i++) list.set(Arrays.binarySearch(sortX,x[i]), make(x[i]));
        for (int i = 0; i < m; i++) {
            if (t[i] == 1) {
                list.set(Arrays.binarySearch(sortX,x[l[i]]), null);
                x[l[i]] += r[i];
                list.set(Arrays.binarySearch(sortX,x[l[i]]), make(x[l[i]]));
            } else {
                Entry res = list.convolution(Arrays.binarySearch(sortX,l[i]), Arrays.binarySearch(sortX,r[i]));
                out.println(res.prod);
            }
        }
    }

    private Entry make(int x) {return new Entry(1, x, 0);}

    class Entry {
        int num;
        long sum;
        long prod;

        Entry(int num, long sum, long prod) {
            this.num = num; this.sum = sum; this.prod = prod;
        }
    }

    private int[] tois(Integer[] Is) {
        int[] is = new int[Is.length];
        for (int i = 0; i < is.length; i++) is[i] = Is[i];
        return is;
    }
}

class MyScanner {
    private final InputStream in;

    public MyScanner(InputStream in) {
        this.in = in;
    }

    int bufLen;
    int bufPtr;
    byte[] buf = new byte[1024];

    public int read() {
        if (bufLen == -1)
            throw new InputMismatchException();
        if (bufPtr >= bufLen) {
            bufPtr = 0;
            try {
                bufLen = in.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (bufLen <= 0)
                return -1;
        }
        return buf[bufPtr++];
    }

    public int nextInt() {
        int c = read();
        if (c == -1) throw new NoSuchElementException();
        while (c != '-' && (c < '0' || '9' < c)) {
            c = read();
            if (c == -1) throw new NoSuchElementException();
        }
        if (c == '-') return -nextInt();
        int res = 0;
        do {
            res *= 10;
            res += c - '0';
            c = read();
        } while ('0' <= c && c <= '9');
        return res;
    }


    }

class MyPrintWriter {
    PrintWriter out;

    public MyPrintWriter(OutputStream outputStream) {
        out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public MyPrintWriter(Writer writer) {
        out = new PrintWriter(writer);
    }

    public void println(Object... os) {
        for (int i = 0; i < os.length - 1; i++) {
            out.print(os[i]);
            out.print(' ');
        }
        out.println(os[os.length - 1]);
    }

    public void close() {
        out.close();
    }

    }

abstract class SegTreeSemigroup<V> {
    /**
     * The operation is required to be associative, where as is not required to be commutative.
     */
    protected abstract V operate(V left, V right);

    /**
     * identity I must satisfy both conditions operate(x,I) = x and operate(I,x) = x for any x in V.
     */
    protected abstract V identity();

    final int n;

    // root : 0
    // parent : (i-1)/2
    // left,right : 2*i+1, 2*i+2
    // leaf : i >= n-1
    final V[] answer;
    final int[] left;
    final int[] right;

    public SegTreeSemigroup(int N) {
        n = Integer.highestOneBit(N) << 1;
        answer = (V[]) new Object[n * 2 - 1];
        Arrays.fill(answer, identity());
        left = new int[n * 2 - 1];
        right = new int[n * 2 - 1];
        init(0, 0, n);
    }

    private void init(int pos, int left, int right) {
        if (pos >= answer.length) return;
        this.left[pos] = left;
        this.right[pos] = right;
        init(pos * 2 + 1, left, (left + right) / 2);
        init(pos * 2 + 2, (left + right) / 2, right);
    }

    public void set(int i, V value) {
        i += n - 1;
        answer[i] = value;
        while (i > 0) {
            i = (i - 1) / 2;
            answer[i] = operate(answer[i * 2 + 1], answer[i * 2 + 2]);
        }
    }

    public V convolution(int from, int to) {
        return convolution(0, from, to);
    }

    V convolution(int pos, int from, int to) {
        if (disjoint(pos, from, to)) return identity();
        if (inner(pos, from, to)) return answer[pos];
        return operate(convolution(pos * 2 + 1, from, to), convolution(pos * 2 + 2, from, to));
    }

    final boolean inner(int pos, int from, int to) {return from <= left[pos] && right[pos] <= to;}

    final boolean disjoint(int pos, int from, int to) { return right[pos] <= from || to <= left[pos]; }
}

