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:
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. Count the sum of distances between all pairs of points that lie on the segment [lj,rj] (lj \le rj). In other words, you should count the sum of: .
Help Yaroslav.

The first line contains integer n - the number of points (1 \le n \le 105). The second line contains distinct integers x1,x2,...,xn - the coordinates of points (|xi| \le 109).

The third line contains integer m - the number of queries (1 \le m \le 105). The next m lines contain the queries. The j-th line first contains integer tj (1 \le tj \le 2) - the query type. If tj=1, then it is followed by two integers pj and dj (1 \le pj \le n,|dj| \le 1000). If tj=2, then it is followed by two integers lj and rj (-109 \le lj \le rj \le 109).

It is guaranteed that at any moment all the points have distinct coordinates.

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.