Задача C. Количество инверсий последовательнсти

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Пара элементов (Ai, Aj) последовательности AN называется инверсией, если Ai > Aj и i < j.

Напишите программу, которая по заданной последовательности AN посчитает количество инверсий.

Формат входного файла

В первой строке входного файла содержится число N — количество элементов последовательности

Последующие N целых чисел задают саму последовательность

Формат выходного файла

В выходном файле должно содержаться единственное число — количество инверсий входной последовательности.

Ограничения

2 ≤ N ≤ 105

0 ≤ Ai ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
7 1 2 5 9 13 16 20
0
2
9
1 1 2 3 8 6 1 9 9
5

0.071s 0.013s 13