Although she is normally the serious type, when she is alone at night, in her private room in the Academy, Ellis secretly logs into her red-rated coder account on Topcoder and Codeforces. Of course, we will respect her privacy and keep her handle secret because she doesn't want people stalking her.

Ever so persistent, you somehow managed to get her contact information. However, Ellis will only talk to coders who are also good problem solvers — as such, she has presented you with a problem. The problem is as follows:

Given an array ~A~ (with 1-based indexing) of length ~N~, for each of ~Q~ queries count the number of pairs of indices ~p, q~ such that ~A_p > A_q~ and ~p < q~ and ~1 \le i \le p, q \le j \le N~. In other words, count the number of inversions in the subarray ~A_i, A_{i+1}, \dots, A_j~.

Afraid of losing this once-in-a-lifetime chance of communicating with Ellis, you quickly open a text editor and start coding. Wait, you should probably read the input and output specifications first…

Input Specification

The first line of input will have ~N~.

The second line of input will have ~A_1, A_2, \dots, A_N~, each separated by a single space.

The third line of input will have ~Q~.

The next ~Q~ lines of input will each have a pair ~i~ and ~j~ separated by a single space.

Output Specification

For each query, output the answer on its own line.

Constraints

~2 \le N \le 100\,000~

~1 \le A_k \le 2\,000\,000\,000~ ~(1 \le k \le N)~

~1 \le Q \le 100\,000~

~1 \le i \le j \le N~

Sample Input

5
4 3 3 2 1
15
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5

Sample Output

0
1
2
5
9
0
0
2
5
0
1
3
0
1
0