Подсчёт инверсий
Когда-то в таинственной стране жил мудрый волшебник по имени Мерлин. Он обладал необычным даром различать скрытые закономерности в перестановках. Больше всего Мерлина интересовало понятие инверсий в перестановке.
Инверсией в перестановке называется пара элементов (ai, aj), для которой i < j и ai > aj. Количество инверсий показывает, насколько данная последовательность чисел отклоняется от упорядоченного по возрастанию вида.
Чтобы испытать навыки начинающих программистов, Мерлин предложил им задачу: given a permutation of integers from 1 to n, необходимо вычислить, сколько в ней инверсий.
Входные данные
Первая строка содержит одно целое число n (1 ≤ n ≤ 100 000), указывающее размер перестановки. Во второй строке находятся n целых чисел, разделённых пробелами, которые образуют искомую перестановку.
Выходные данные
Выведите одно целое число — количество инверсий в данной перестановке.
Примеры
Input | Output |
5
3 1 4 2 5 | 3 |
4
1 2 3 4 | 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB