Problem
n개 요소의 순열이 주어집니다.
l에서 r까지의 순열 하위 세그먼트에 대한 반전 수에 대한 m 쿼리에 응답합니다.
반전은 i < j 및 a
i > a
j, 여기서 a
i는 순열의 i번째 요소입니다.
입력:
첫 번째 줄에는 숫자 n(1 <= n <= 10
5)이 포함됩니다.
두 번째 줄은 n개 요소의 순열을 포함합니다(순열의 요소는 1에서 n까지 쌍으로 구별되는 정수입니다).
세 번째 줄에는 숫자 m이 포함됩니다(1 <= m <= 10
5).
다음 m행에는 쿼리의 범위(1 <= l, r <= n)인 두 개의 정수 l 및 r이 포함됩니다.
출력:
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 |