Стрижка волосся
Фермер Джон, втомившись від свого неслухняного чуба, вирішив підстригтися. У нього є n пасом волосся, розташованих у ряд, і пасмо i має початкову довжину a[i] мікрометрів. Ідеальною для нього є ситуація, коли довжина волосся монотонно зростає, тому він визначає "поганий вигляд" свого волосся як кількість інверсій: пар (i, j), де i < j і a[i] > a[j].
Для кожного j = 0, 1, ..., n − 1, Джон хоче знати, наскільки "погано" виглядає його волосся, якщо всі пасма, довші за j, будуть зменшені до довжини рівно j.
(Цікавий факт: середня людська голова дійсно має близько 10^5 волосин!)
Вхідні дані
Перша строка містить число n (1 ≤ n ≤ 10^5). Друга строка містить числа a[1], a[2], ..., a[n] (0 ≤ a[i] ≤ n).
Вихідні дані
Для кожного j = 0, 1, ..., n − 1, виведіть "поганий вигляд" волосся Джона в окремому рядку. Зверніть увагу, що великий розмір цілих чисел у цій задачі може вимагати використання 64-бітних цілих типів даних (наприклад, long long у C/C++).
Приклад
Четвертий рядок вихідних даних описує кількість інверсій, коли волосся Джона зменшуються до довжини 3. Тоді 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].