Недавно Дима познакомился с Сашей в филателистическом магазине, и с тех пор они собирают монеты вместе. Их любимое занятие — сортировать коллекции монет. Саше нравится порядок, поэтому он хочет, чтобы монеты были расположены в ряд, причём сначала шли монеты, вышедшие из обращения, а потом монеты, всё ещё находящиеся в обращении.
Для упорядочивания монет Дима использует алгоритм, один шаг которого выглядит следующим образом:
- Дима просматривает все монеты слева направо;
- если он видит, что i-я монета ещё в ходу, а (i + 1)-я уже вышла из обращения, то он меняет эти две монеты местами, и продолжает смотреть на монеты дальше, начиная с (i + 1)-й.
Дима повторяет этот шаг до тех пор, пока не окажется, что на очередном шаге не произошло ни одного обмена. Сложностью упорядочивания Дима называет количество шагов, которые ему требуются в соответствии с процедурой, описанной выше, то есть, количество раз, которое он будет начинать просматривать монеты с начала. В частности, для уже упорядоченной исходной последовательности монет сложность упорядочивания равна единице.
Сегодня Саша в очередной раз позвал Диму в гости, чтобы предложить ему следующую игру. Сначала он выложил в ряд перед Димой n монет, все из которых вышли из обращения. Затем Саша n раз выбирает какую-то из монет, которая вышла из обращения, и заменяет её на монету, которая находится в обращении. В ходе этого процесса Саша постоянно интересуется у Димы, какова на данный момент сложность упорядочивания последовательности.
Задачу усложняет тот факт, что Диме нельзя трогать монеты, и поэтому определять сложность упорядочивания ему приходится в уме. Помогите Диме справиться с этим заданием.
Выходные данные
Выведите n + 1 чисел a0, a1, ..., an, где a0 — сложность упорядочивания последовательности в начале, a1 — сложность упорядочивания после замены одной монеты и так далее.
Примечание
Разберём первый пример. Будем обозначать за O монету, вышедшую из обращения, а за X — монету в обращении.
Изначально в ряду лежат монеты, вышедшие из обращения, поэтому Дима один раз просмотрит их слева направо, и не совершит никаких обменов.
После замены Сашей первой монеты на находящуюся в обращении Дима на первом шаге алгоритма три раза поменяет эту монету с последующей, после чего один раз просмотрит монеты и завершит процесс:
XOOO → OOOX
После замены Сашей третьей монеты действия Димы выглядят следующим образом:
XOXO → OXOX → OOXX
После замены Сашей четвёртой монеты действия Димы выглядят следующим образом:
XOXX → OXXX
Наконец, после замены Сашей второй монеты весь ряд оказывается состоящим из монет, находящихся в обращении, и Дима один раз просмотрит ряд слева направо.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 3 4 2
|
1 2 3 2 1
|
|
2
|
8
6 8 3 4 7 2 1 5
|
1 2 2 3 4 3 4 5 1
|