Стрижка волосся#10310
Фермер Джон, втомившись від свого неслухняного чуба, вирішив підстригтися. У нього є пасм волосся, розташованих у ряд, і пасмо має початкову довжину a_i мікрометрів. Ідеальною для нього є ситуація, коли довжина волосся монотонно зростає, тому він визначає "поганий вигляд" свого волосся як кількість інверсій: пар , де i < j і a_i > a_j.
Для кожного j = 0, 1, \ldots, n - 1, Джон хоче знати, наскільки "погано" виглядає його волосся, якщо всі пасма, довші за , будуть зменшені до довжини рівно .
(Цікавий факт: середня людська голова дійсно має близько 10^5 волосин!)
Перший рядок містить число (1 \le n \le 10^5). Другий рядок містить числа a_1, a_2, \ldots, a_n (0 \le a_i \le n).
Для кожного j = 0, 1, \ldots, n - 1, виведіть "поганий вигляд" волосся Джона в окремому рядку. Зверніть увагу, що великий розмір цілих чисел у цій задачі може вимагати використання 64-бітних цілих типів даних (наприклад, long long у C/C++).
\begin{example}\exmark{53 2 3 3 0}\exmark{04455}\end{example}
Приклад 1
Четвертий рядок вихідних даних описує кількість інверсій, коли волосся Джона зменшується до довжини . Тоді A = [3, 2, 3, 3, 0] має п'ять інверсій: a_1 > a_2, a_1 > a_5, a_2 > a_5, a_3 > a_5 і a_4 > a_5.