Sherlock and Watson

Submit solution
Points: 100 (partial)
Time limit: 5.0s
Java 8 10.0s
Python 15.0s
Memory limit: 64M
Authors:
luismo, leocar, leo, eliogovea
Problem type
Allowed languages
Ada, BrainF***, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

After a long series of jobless days, Sherlock and Watson frustated by the lack of new cases, decide to turn their minds toward something interesting like solving few logical problems. One of the problems they have to solve now is as follows:

Given an A array of size 1\leq N \leq 10^5 and a list of 1\leq Q \leq 10^5 queries, where each query has two L and R numbers, find for each query the number of investments in the subarray located between the L and R positions (both inclusive) of the A array. Settlement indices begin at 1 and 1\leq L \leq R \leq N. For an A array, two elements A[i] and A[j] form an inversion if A[i] > A[j] and i<j. Help them solve this problem.

Input

The first line contains a single integer, the length N of the array. The second line contains N integers 1 \leq A[i] \leq 10^6 separated by a space. The third line has a single integer Q. The following Q lines contain 2 integers L and R separated by a space and represent the query information.

Output

Output Q lines, ith line having a single integer, the answer to the ith query

Example Input:

7
7 9 3 5 1 6 4
4
1 4
3 5
1 2
1 7

Output:

4
2
0
14

Comments


  • -6
    Primervirgen  commented on Aug. 18, 2019, 4:17 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -3
    Primervirgen  commented on Aug. 9, 2019, 7:37 a.m.

    Alguien me dice q algoritmo c utiliza para este problema? Puede ser una DP, o lo otro podría ser Segment-tree???


    • 8
      Leonardo  commented on Aug. 15, 2019, 3:36 a.m.

      Mo's algorithm con ABI