Поликарп планирует провести нагрузочное тестирование своего нового проекта Fakebook. Он уже договорился с друзьями, чтобы в определённые моменты времени они посылали запросы в Fakebook. Тестирование продлится n минут, в i-ю минуту друзья пошлют ai запросов.
Поликарп планирует протестировать Fakebook под особым видом нагрузки. В случае попадания информации о Fakebook в СМИ Поликарп надеется на монотонный рост нагрузки, который сменится монотонным убыванием интереса к сервису. Такой профиль нагрузки и собирается протестировать Поликарп во время нагрузочного теста.
Какое минимальное количество запросов придется дополнительно сделать Поликарпу, чтобы сначала нагрузка на сервер строго возрастала, а затем строго убывала? Как возрастающая часть, так и убывающая часть могут быть пустыми (то есть отсутствовать). Убывание должно сразу же сменить возрастание, например, участок одинаковых подряд значений нагрузки недопустим.
К примеру, если нагрузка описывается одним из массивов [1, 2, 8, 4, 3], [1, 3, 5] или [10], то такой профиль нагрузки устраивает Поликарпа (в каждом из этих случаев сначала идёт участок строгого возрастания, затем тут же строго убывания). Если нагрузка описывается одним из массивов [1, 2, 2, 1], [2, 1, 2] или [10, 10], то такой профиль нагрузки не устраивает Поликарпа.
Помогите Поликарпу сделать минимальное количество дополнительных запросов, чтобы получившийся профиль нагрузки его устраивал. Дополнительные запросы Поликарп может делать в любом количестве в любые минуты от 1 до n.
Выходные данные
Выведите минимальное количество дополнительных запросов, которые надо сделать Поликарпу, чтобы нагрузка сначала строго возрастала, а затем сразу строго убывала.
Примечание
В первом примере Поликарп должен сделать два дополнительных запроса в третью минуту и четыре — в четвёртую. Тогда получившаяся нагрузка примет вид: [1, 4, 5, 6, 5]. Суммарно будет сделано 6 дополнительных запросов.
Во втором примере достаточно один раз сделать дополнительный запрос в третью минуту, поэтому ответ равен 1.
В третьем примере нагрузка уже удовлетворяет всем описанным в условии требованиям, поэтому ответ 0.