Однажды утром Фермер Джон проснулся от звуков дробления древесины.
Это коровы ломали амбар.
ФД рассердился. Он приделал к стене счётчик дней с последнего слома.
Если слом случился утром, счётчик покажет 0. Если последний слом случился 3
дня назад, счётчик показывает 3. ФД тщательно записывал значение счётчика
каждый день.
В конце года ФД решил действовать. Однако с логом некоторые проблемы.
ФД хочет определить, сколько слово зафиксировано. Однако он подозревает,
что коровы подделали его лог и всё в чём он уверен, что он начало лог в день
слома. Помогите ему определить, для каждого количества сломов какое минимальное
количество записей должно быть подделано.
ФОРМАТ ВВОДА (файл taming.in):
Первая строка ввода содержит одно целое число
\(N\) (
\(1 \leq N \leq 100\)),
обозначающее количество дней, с дня когда ФД начал логгирование.
Вторая строка содержит \(N\) целых чисел, разделённых одиночными пробелами.
\(i\)-ое число это неотрицательное целое \(a_i\) (не более 100), указывающее
что в день \(i\) на счётчике было \(a_i\) если коровы не подделали эту запись в логе.
ФОРМАТ ВЫВОДА (файл taming.out):
Вывод состоит из \(N\) целых чисел, по одному в строке. \(i\)-ое целое число
должно содержать минимум из всех возможных последовательностей с \(i\) сломами
количества записей, которые несостоятельны в этой последовательности.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 1 2 0 0 1
|
4
2
1
2
3
4
|