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