Имеется стопка оладий. Необходимо сделать из них правильную стопку: каждая оладья должна быть не больше всех оладий, находящихся под нею. Все оладьи круглые, поэтому размер оладьи определяется ее диаметром.
Сортировка стопки осуществляется серией “переворотов” оладий. Переворот заключается в том, что вы помещаете лопатку между двумя оладьями и переворачиваете всю стопку, оказавшуюся на лопатке, то есть меняете порядок следования оладий над лопаткой на обратный.
Стопка определяется заданием диаметра каждой оладьи в стопке в порядке следования (сверху вниз). Переворачивание определяется количеством оладий, которое переворачивается. Например, из стопки 7 3 9 1 5 переворачиванием трех оладий получится стопка 9 3 7 1 5.
Вам дана стопка оладий, выведите последовательность переворачиваний (то есть количество оладий, которое нужно переворачивать за один раз), сортирующую данную стопку.
Входные данные
Первая строка входных данных содержит натуральное число N (1 ≤ N ≤ 1000) – количество оладий в стопке. Далее идет N натуральных чисел, не превосходящих 10
9 – размеры оладий в стопке (сверху вниз).
Выходные данные
Ваша программа должна вывести последовательность натуральных чисел, не превосходящих N, соответствующую количеству оладий, которое необходимо переворачивать для правильной сортировки стопки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 3 2
|
2
3
2
|