Задача І знову бульбашка (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 чисел, кожне з яких дорівнює кількості операцій перестановки, що були проведені над числом, яке стояло на цьому місці у вихідній таблиці.

Приклад вхідних та вихідних даних.