Problem
n 要素の順列が与えられます。
l から r への順列サブセグメントの反転数に関する m クエリに答えます。
反転は、i < であるようなインデックス i、j のペアです。 j と a
i > a
j、ここで a
i は順列の i 番目の要素です。
入力:
最初の行には、数値 n (1 <= n <= 10
5) が含まれています。
2 行目には、n 個の要素の順列が含まれています (順列の要素は、1 から n までの対ごとに異なる整数です)。
3 行目には数値 m (1 <= m <= 10
5) が含まれます。
次の m 行には、2 つの整数 l と r が含まれます - クエリの境界 (1 <= l、r <= n)。
出力:
これらのクエリに対する回答を m 行出力します。
例:
<本体>
| 入力 |
出力 |
5
4 5 2 3 1
3
1 3
3 5
15 |
2
2
8 |
6
5 2 4 3 1 6
3
46
25
15 |
1
4
8 |