Задача И снова пузырек (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]<=109,все элементы различны), разделенные пробелами.
Программа bubblesort выводит на экран (стандартное устройство вывода) N чисел, каждое из которых является количеством операций перестановки, проведенных над числом, которое стояло на этом месте в исходной таблице.
Пример входных и выходных данных.
|
Ввод |
Вывод |
|
4 1 2 5 4 |
3 3 2 2 |