Фермер Джон решил постричься.
У него есть \(N\) прядей волос (\(1\le N\le 10^5\)), расположенных последовательно.
Прядь \(i\) имеет изначально длину \(A_i\) микрометров (\(0\le A_i\le N\)).
В идеале ФД хочет, чтобы его пряди монотонно возрастали по длине. Поэтому он
определил "негодность" волос как количество инверсий то есть пар \((i,j)\)
таких, что \(i < j\) и \(A_i > A_j\).
Для каждого \(j=0,1,\ldots,N-1\), ФД хочет узнать "негодность" его волос
если все пряди с длиной больше чем \(j\) будут уменьшены до длины ровно \(j\).
ФОРМАТ ВВОДА (файл haircut.in):
Первая строка содержит
\(N\).
Вторая строка содержит \(A_1,A_2,\ldots,A_N.\)
ФОРМАТ ВЫВОДА (файл haircut.out):
Для каждого
\(j=0,1,\ldots,N-1\), выведите "негодность" волос ФД в новой строке.
Заметим, ответы могут потребовать 64-битного типа данных
(например, "long long" в C/C++).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 2 3 3 0
|
0
4
4
5
7
|