Inversion Queries

長さの数列と、クエリの数、及び個のクエリが与えられます。各クエリには、2つの整数とが与えられます。各クエリで以下の値を答えてください。

• 数列の部分配列の転倒数。

転倒数とはかつとなるの組の数です。

• 入力は全て整数

N
A_1 A_2 .. A_N
Q
L_1 R_1
...
L_Q R_Q

Pythonの方はPyPyで提出することをお勧めします。

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

1
2
4

２番目のクエリでの転倒数はの２つです。

３番目のクエリでの転倒数はの４つです。

5
10 4 6 4 4
5
4 5
2 5
1 5
3 4
3 5

0
2
6
1
2