Однажды утром Фермер Джон проснулся от звуков дробления древесины. Это коровы ломали амбар.

ФД рассердился. Он приделал к стене счётчик дней с последнего слома. Если слом случился утром, счётчик покажет 0. Если последний слом случился 3 дня назад, счётчик показывает 3. ФД тщательно записывал значение счётчика каждый день.

В конце года ФД решил действовать. Однако с логом некоторые проблемы.

ФД хочет определить, сколько сломов зафиксировано. Однако он подозревает, что коровы подделали его лог и всё в чём он уверен, что он начал лог в день слома. Помогите ему определить, для каждого количества сломов какое минимальное количество записей должно быть подделано.

Входные данные

Первая строка содержит одно целое число n (1 ≤ n ≤ 100), обозначающее количество дней, с дня когда ФД начал логгирование.

Вторая строка содержит n целых чисел, разделённых одиночными пробелами. i-ое число это неотрицательное целое ai (не более 100), указывающее что в день i на счётчике было ai если коровы не подделали эту запись в логе.

Выходные данные

Вывод состоит из n целых чисел, по одному в строке. i-ое целое число должно содержать минимум из всех возможных последовательностей с i сломами количества записей, которые несостоятельны в этой последовательности.

Пример

Если был только один слом, то корректный лог должен выглядеть 0 1 2 3 4 5. Имеется 4 записи, отличающиеся от этого лога.

Если было 2 слома, корректный лог может выглядеть как 0 1 2 3 0 1, и есть 2 записи, отличающиеся от данного лога, в этом случае сломы случились на первый и пятый дни.

Если было 3 слома, тогда корректный лог может выглядеть как 0 1 2 0 0 1, и только 1 запись отличается от данного лога. В этом случае сломы случились на первый, четвёртый и пятый дни.

И так далее.