Приборкання стада (Золото)#10413
Рано вранці Фермер Джон прокинувся від тріску дерева, що ламалося. Це були корови, і вони знову вириалися з хліва!
Фермеру Джону до смерті набридли ранкові втечі корів, і він вирішив, що з нього досить: настав час вживати жорстких заходів. Він прибив до стіни хліва лічильник, який показує кількість днів, що минули з моменту останньої втечі. Так, якщо втеча сталася вранці, то цього дня лічильник показує ; якщо остання втеча була дні тому, лічильник показує . Фермер Джон кожного дня ретельно записував показання лічильника у журнал.
Настав кінець року, і Фермер Джон готовий підбити підсумки. Корови за все заплатять, каже він! Але щось у його журналі виглядає не зовсім правильно...
Фермер Джон хоче з'ясувати, скільки втеч сталося з того моменту, як він почав вести журнал. Однак він підозрює, що корови підробили записи в журналі, і точно знає лише одне: він почав вести журнал у день втечі. Допоможіть йому визначити для кожної можливої кількості втеч з початку ведення журналу мінімальну кількість записів, які повинні були бути підробленими.
Перший рядок містить одне ціле число n~(1 \le n \le 100) — кількість днів з того моменту, як Фермер Джон почав записувати показання лічильника втеч.
Другий рядок містить цілих чисел a_1, a_2, \ldots, a_n~(0 \le a_i \le 100), де a_i — показання лічильника в -й день, якщо тільки корови не підробили запис за цей день.
Виведіть цілих чисел, по одному в рядку. -е число повинно дорівнювати мінімальній кількості записів журналу, які не узгоджуються з послідовністю втеч, що містить рівно втеч. Мінімум береться за всіма такими послідовностями.
Приклад 1
Якщо втеча була лише , то правильний журнал мав би вигляд 0, 1, 2, 3, 4, 5, що відрізняється від заданого журналу в записах.
Якщо втеч було , то правильний журнал міг би мати вигляд 0, 1, 2, 3, 0, 1, що відрізняється від заданого журналу в записах. У цьому випадку втечі сталися в перший і п'ятий дні.
Якщо втеч було , то правильний журнал міг би мати вигляд 0, 1, 2, 0, 0, 1, що відрізняється від заданого журналу лише в записі. У цьому випадку втечі сталися в перший, четвертий і п'ятий дні.
І так далі.