Стрижка волос
Устав от своего упрямого чуба, фермер Джон решил подстричься. Его 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].