Дана перестановка из n элементов.
Ответьте на m запросов про число инверсий для подотрезка перестановки от l до r.
Инверсией называется пара индексов i, j такая, что i < j и a
i > a
j, где a
i - это i-й элемент перестановки.
Входные данные:
В первой строке задано число n (1 <= n <= 10
5).
Во второй строке задана перестановка из n элементов (элементы перестановки - попарно различные целые числа от 1 до n).
В третьей строке задано число m (1 <= m <= 10
5).
В последующих m строках содержится по два числа l и r - границы запроса (1 <= l, r <= n).
Выходные данные:
Выведите m строк - ответы на данные запросы.
Примеры:
| Входные данные |
Выходные данные |
5
4 5 2 3 1
3
1 3
3 5
1 5 |
2
2
8 |
6
5 2 4 3 1 6
3
4 6
2 5
1 5 |
1
4
8 |