問題

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

  • 数列AAの部分配列AL,AL+1,...ARA_L, A_{L+1}, ... A_{R}の転倒数。

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

制約

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

入力

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

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

入力例1

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

出力例1

1
2
4

2番目のクエリでの転倒数は(A3,A5),(A4,A5)(A_3, A_5), (A_4, A_5)の2つです。

3番目のクエリでの転倒数は(A1,A2),(A1,A5),(A3,A5),(A4,A5)(A_1, A_2), (A_1, A_5), (A_3, A_5), (A_4, A_5)の4つです。

入力例2

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

出力例2

0
2
6
1
2

提出


Go (1.21)