Вывести значение счастья Пети, если он выполнит заданную операцию k раз

Перестановкой назовем массив, состоящий из n различных целых чисел от 0 до n − 1 в произвольном порядке. Например, [ 2 , 1 , 0 , 4 , 3 ] является перестановкой, а [ 0 , 1 , 1 ] и [ 0 , 2 ] — нет. На день рождения Пете подарили перестановку p 1 , p 2 , … , p n . Счастье Пети определяется как количество пар ( i , j ) , таких что 1 ≤ i < j ≤ n и p i > p j . Пете разрешено многократно выполнять следующую операцию: переместить первый элемент перестановки в ее конец. Например, если изначально у Пети была перестановка [ 1 , 2 , 0 , 4 , 3 ] , то после применения операции у него будет перестановка [ 2 , 0 , 4 , 3 , 1 ] . Для каждого k от 0 до n − 1 выведите значение счастья Пети, если он выполнит данную операцию k раз. Формат входных данных Первая строка содержит число n ( 2 ≤ n ≤ 3 ⋅ 10 5 ) — размер перестановки. Вторая строка содержит записанные через пробел числа p 1 , p 2 , … , p n — перестановку чисел от 0 до n − 1 . Формат выходных данных В следующих n строках выведите числа a 0 , a 1 , … , a n − 1 , где a k — счастье Пети при условии, что он k раз переместил первый элемент перестановки в ее конец.
Примеры
Входные данные
5
0 1 2 3 4
Выходные данные
0
4
6
6
4
Входные данные
10
0 8 1 2 7 4 5 3 6 9
Выходные данные
13
22
15
22
27
22
23
22
25
22
Входные данные
5
0 4 1 3 2
Выходные данные
4
8
4
6
4

0