Задача №113728. Сортировка монет
Недавно Дима познакомился с Сашей в филателистическом магазине, и с тех пор они собирают монеты вместе. Их любимое занятие — сортировать коллекции монет. Саше нравится порядок, поэтому он хочет, чтобы монеты были расположены в ряд, причём сначала шли монеты, вышедшие из обращения, а потом монеты, всё ещё находящиеся в обращении.
Для упорядочивания монет Дима использует следующий алгоритм: за один шаг он просматривает все монеты слева направо, и если он видит, что \(i\)-я монета ещё в ходу, а \((i+1)\)-я уже вышла из обращения, то он меняет эти две монеты местами, и продолжает смотреть на монеты дальше, начиная с \((i+1)\)-й. Дима повторяет эту операцию до тех пор, пока не окажется, что на очередном шаге не произошло ни одного обмена. Сложностью упорядочивания Дима называет количество шагов, которые ему требуются в соответствии с процедурой, описанной выше, то есть, количество раз, которое он будет начинать просматривать монеты с начала. В частности, для уже упорядоченной исходной последовательности монет сложность упорядочивания равна единице.
Сегодня Саша в очередной раз позвал Диму в гости, чтобы предложить ему следующую игру. Сначала он выложил в ряд перед Димой \(n\) монет, все из которых вышли из обращения. Затем Саша \(n\) раз выбирает какую-то из монет, которая вышла из обращения, и заменяет её на монету, которая находится в обращении. В ходе этого процесса Саша постоянно интересуется у Димы, какова на данный момент сложность упорядочивания последовательности.
Задачу усложняет тот факт, что Диме нельзя трогать монеты, и поэтому определять сложность упорядочивания ему приходится в уме. Помогите Диме справиться с этим заданием.
В первой строке задано целое число \(n\) (\(1 \leq n \leq 300\,000\)) — количество монет, которые Саша выложил в ряд перед Димой.
Следующая строка содержит \(n\) целых различных чисел \(p_1, p_2, \ldots, p_n\) (\(1 \leq p_i \leq n\)) — позиции монет, если смотреть слева направо, которые Саша меняет на монеты, находящиеся в ходу. Сначала Саша заменяет монету, находящуюся на позиции \(p_1\), затем монету, находящуюся на позиции \(p_2\) и так далее.
Выведите \(n + 1\) чисел \(a_0, a_1, \ldots, a_n\), где \(a_0\) — сложность упорядочивания последовательности в начале, \(a_1\) — сложность упорядочивания после замены одной монеты и так далее.
Разберём первый пример. Будем обозначать за O монету, вышедшую из обращения, а за X — монету в обращении.
Изначально в ряду лежат монеты, вышедшие из обращения, поэтому Дима один раз просмотрит их слева направо, и не совершит никаких обменов.
После замены Сашей первой монеты на находящуюся в обращении Дима на первом шаге алгоритма три раза поменяет эту монету с последующей, после чего один раз просмотрит монеты и завершит процесс:
XOOO -> OOOX
После замены Сашей третьей монеты действия Димы выглядят следующим образом:
XOXO -> OXOX -> OOXX
После замены Сашей четвёртой монеты действия Димы выглядят следующим образом:
XOXX -> OXXX
Наконец, после замены Сашей второй монеты весь ряд оказывается состоящим из монет, находящихся в обращении, и Дима один раз просмотрит ряд слева направо.
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