Inversion Queries

問題

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

• 数列$A$の部分配列$A_L, A_{L+1}, ... A_{R}$の転倒数。

転倒数とは$i < j$かつ$A_i > A_j$となる$(i,j)$の組の数です。

制約

• $2 \leqq N \leqq 10^4$
• $1 \leqq A_i \leqq 10^5$
• $1 \leqq Q \leqq 10^5$
• $1 \leqq L < R \leqq N$
• 入力は全て整数

入力

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

２番目のクエリでの転倒数は$(A_3, A_5), (A_4, A_5)$の２つです。

３番目のクエリでの転倒数は$(A_1, A_2), (A_1, A_5), (A_3, A_5), (A_4, A_5)$の４つです。

入力例２

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

出力例２

0
2
6
1
2