Поликарп планирует провести нагрузочное тестирование своего нового проекта Fakebook. Он уже договорился с друзьями, чтобы в определённые моменты времени они посылали запросы в Fakebook. Тестирование продлится n минут, в i-ю минуту друзья пошлют a_i запросов.

Поликарп планирует протестировать Fakebook под особым видом нагрузки. В случае попадания информации о Fakebook в СМИ Поликарп надеется на монотонный рост нагрузки, который сменится монотонным убыванием интереса к сервису. Такой профиль нагрузки и собирается протестировать Поликарп во время нагрузочного теста.

Какое минимальное количество запросов придется дополнительно сделать Поликарпу, чтобы сначала нагрузка на сервер строго возрастала, а затем строго убывала? Как возрастающая часть, так и убывающая часть могут быть пустыми (то есть отсутствовать). Убывание должно сразу же сменить возрастание, например, участок одинаковых подряд значений нагрузки недопустим.

К примеру, если нагрузка описывается одним из массивов [1, 2, 8, 4, 3], [1, 3, 5] или [10], то такой профиль нагрузки устраивает Поликарпа (в каждом из этих случаев сначала идёт участок строгого возрастания, затем тут же строго убывания). Если нагрузка описывается одним из массивов [1, 2, 2, 1], [2, 1, 2] или [10, 10], то такой профиль нагрузки не устраивает Поликарпа.

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