Модуль: Алгоритм Мо


Задача

4 /4


Инверсии на отрезке

Задача

Дана перестановка из n элементов.
Ответьте на m запросов про число инверсий для подотрезка перестановки от l до r.
Инверсией называется пара индексов i, j такая, что i < j и ai > aj, где ai - это i-й элемент перестановки.

Входные данные:
В первой строке задано число n (1 <= n <= 105).
Во второй строке задана перестановка из n элементов (элементы перестановки - попарно различные целые числа от 1 до n).
В третьей строке задано число m (1 <= m <= 105).
В последующих 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



time 5000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6412
Комментарий учителя