Задача І знову бульбашка (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 |