Задача И снова пузырек (bubblesort).

Колыван решил срочно собрать со всех своих должников долги. Чтобы не забыть размер долга каждого из них, он записал в большую таблицу количество золотых слитков, которые ему должен каждый из должников. Теперь Колывану необходимо отсортировать эту таблицу, чтобы взимать долги строго в порядке их убывания, а никаких алгоритмов сортировки он не знает. Колывану удалось украсть у Киевского князя секретный документ, содержащий описание алгоритма сортировки следующего вида:

для k от 1 до N-1

для j от 1 до N-k

если A[j] < A[j+1]

переставить A[j] и A[j+1]

Начав выполнять перестановки по описанному алгоритму, Колыван понял, что работа выполняется очень медленно, и хочет оценить необходимое время для ее выполнения. Помогите Колывану оценить время работы сортировки, подсчитав для каждого элемента таблицы количество операций перестановки, проведенных над ним.

Формат ввода/вывода.

Программа bubblesort считывает с клавиатуры (стандартного устройства ввода) целое число N (1<=N<=100000) – количество сортируемых чисел; а затем N целых чисел – элементы сортируемой таблицы (1<=A[i]<=10⁹,все элементы различны), разделенные пробелами.

Программа bubblesort выводит на экран (стандартное устройство вывода) N чисел, каждое из которых является количеством операций перестановки, проведенных над числом, которое стояло на этом месте в исходной таблице.

Пример входных и выходных данных.