Стрижка волос
Стрижка волос
Устав от своего упрямого чуба, фермер Джон решил подстричься. Его n прядей волос уложены в линию, а прядь i изначально имеет длину ai
микрометров. В идеале он хочет, чтобы его волосы монотонно увеличивались в длине, поэтому он определяет "плохой вид" своих волос как количество инверсий: пар (i, j) таких что i < j и ai
> aj
.
Для каждого j = 0, 1,..., n − 1 ФД хотел бы знать, насколько плохой вид у его волос, если все пряди длиной больше j будут уменьшены до длины точно j.
(Забавный факт: средняя человеческая голова действительно имеет около 105
волос!)
Входные данные
Первая строка содержит число n (1 ≤ n ≤ 105
). Вторая строка содержит числа a1
, a2
, ..., an
(0 ≤ ai
≤ n).
Выходные данные
Для каждого j = 0, 1, ..., n − 1, выведите "плохой вид" волос ФД в отдельной строке. Обратите внимание, что большой размер целых чисел в этой задаче может потребовать использования 64-битных целочисленных типов данных (например, long long в C/C++).
Пример
Четвертая строка выходных данных описывает количество инверсий, когда волосы ФД уменьшаются до длины 3. Тогда A = [3, 2, 3, 3, 0] имеет пять инверсий: a1
> a2
, a1
> a5
, a2
> a5
, a3
> a5
и a4
> a5
.
5 5 2 3 3 0
0 4 4 5 7