Sherlock and Inversions
Tag(s):

## Algorithms, Hard, Sqrt-Decomposition

Problem
Editorial
Analytics

Watson gives to Sherlock an array of N integers denoted by A1, A2 ... AN.
Now he gives him Q queries of form Li, Ri. For each such query Sherlock has to report the number of inversions in subarray denoted by [Li, Ri].

Inversions in a subarray denoted by [a, b] are number of pairs (i, j) such that ai < jb and Ai > Aj.

Input
First line contains N and Q. Next line contains N space separated integers denoting array A.
Each of the next Q lines contain two space separated integers denoting Li, Ri.

Output
For each query, print the required answer in one line.

Constraints
20% files: 1 ≤ N, Q ≤ 103
20% files: 1 ≤ N ≤ 103 and 1 ≤ Q ≤ 105
60% files: 1 ≤ N, Q ≤ 105
1 ≤ Ai ≤ 109
1 ≤ LiRiN

SAMPLE INPUT
5 3
1 4 2 3 1
1 2
3 5
1 5

SAMPLE OUTPUT
0
2
5

Explanation

query1: Number of inversions in B = [1, 4] is 0.

query2: Number of inversions in B = [2, 3, 1] are 2 since B>B and B>B.

query3: Number of inversions in original array are 5.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

February Love '15

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Searching
• Basic Programming > Implementation
• Algorithms > Dynamic Programming
• Basic Programming > Implementation