Приручення стада (Золото)
Одного ранку фермер Джон прокинувся від звуків тріскоту деревини. Це корови ламали амбар.
Фермер Джон розлютився. Він прикріпив до стіни лічильник днів з останнього ламання. Якщо ламання сталося сьогодні, лічильник покаже 0. Якщо останнє ламання було 3 дні тому, лічильник покаже 3. Фермер Джон ретельно записував значення лічильника кожного дня.
Наприкінці року фермер вирішив діяти. Проте з його записами виникли деякі проблеми.
Фермер хоче визначити, скільки ламань відбулося. Однак він підозрює, що корови підробили його записи, і єдине, в чому він впевнений, це те, що він почав вести записи в день ламання. Допоможіть йому визначити, для кожної можливої кількості ламань, яка мінімальна кількість записів має бути підроблена.
Вхідні дані
Перший рядок містить одне ціле число n (1 ≤ n ≤ 100), що позначає кількість днів, з яких фермер Джон почав вести записи.
Другий рядок містить n цілих чисел, розділених пробілами. i-е число — це невід'ємне ціле a[i] (не більше 100), що вказує, що в день i на лічильнику було a[i], якщо корови не підробили цей запис.
Вихідні дані
Вивід складається з 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 запис відрізняється від даного логу. У цьому випадку ламання сталися на перший, четвертий і п'ятий дні.
І так далі.