B. Сортировка монет
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Дима познакомился с Сашей в филателистическом магазине, и с тех пор они собирают монеты вместе. Их любимое занятие — сортировать коллекции монет. Саше нравится порядок, поэтому он хочет, чтобы монеты были расположены в ряд, причём сначала шли монеты, вышедшие из обращения, а потом монеты, всё ещё находящиеся в обращении.

Для упорядочивания монет Дима использует алгоритм, один шаг которого выглядит следующим образом:

  1. Дима просматривает все монеты слева направо;
  2. если он видит, что i-я монета ещё в ходу, а (i + 1)-я уже вышла из обращения, то он меняет эти две монеты местами, и продолжает смотреть на монеты дальше, начиная с (i + 1)-й.

Дима повторяет этот шаг до тех пор, пока не окажется, что на очередном шаге не произошло ни одного обмена. Сложностью упорядочивания Дима называет количество шагов, которые ему требуются в соответствии с процедурой, описанной выше, то есть, количество раз, которое он будет начинать просматривать монеты с начала. В частности, для уже упорядоченной исходной последовательности монет сложность упорядочивания равна единице.

Сегодня Саша в очередной раз позвал Диму в гости, чтобы предложить ему следующую игру. Сначала он выложил в ряд перед Димой 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

Наконец, после замены Сашей второй монеты весь ряд оказывается состоящим из монет, находящихся в обращении, и Дима один раз просмотрит ряд слева направо.