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