Ellis Fahrengart

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

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, \ldots, 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

Comments


  • 1
    FatalEagle  commented on March 15, 2015, 1:16 p.m.

    You plagiarized code from Codechef and submitted it without attribution.


    • 1
      kobortor  commented on March 15, 2015, 1:18 p.m.

      Ah but I wrote everything before that submission and I was just frusterated by the 90/100. Can you remove the codechef submission and unban?


      • 1
        Xyene  commented on March 15, 2015, 1:19 p.m.

        Done.