Problem
Cho một hoán vị của n phần tử.
Trả lời m truy vấn về số lần nghịch đảo của một phân đoạn con hoán vị từ l đến r.
Phép nghịch đảo là một cặp chỉ số i, j sao cho i < j và a
i > a
j, trong đó a
i là phần tử thứ i của hoán vị.
Đầu vào:
Dòng đầu tiên chứa số n (1 <= n <= 10
5).
Dòng thứ hai chứa một hoán vị của n phần tử (các phần tử của hoán vị là các số nguyên phân biệt theo cặp từ 1 đến n).
Dòng thứ ba chứa số m (1 <= m <= 10
5).
m dòng tiếp theo chứa hai số nguyên l và r - giới hạn của truy vấn (1 <= l, r <= n).
Đầu ra:
In m dòng - câu trả lời cho những truy vấn này.
Ví dụ:
| Đầu vào |
Đầu ra |
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 |