Турист совершил путешествие вдоль горного хребта. Путешествие длилось n дней, в каждый из которых турист записывал в дневник высоту над уровнем моря; в i-й день высота была равна некоторому целому числу h_i. Турист выбрал для путешествия не слишком крутой маршрут, чтобы вдоль него можно было пройти пешком, поэтому за один день высота изменялась не более, чем на 1, т.е. для всех i от 1 до n - 1 выполнено |h_i - h_i + 1| ≤ 1.

В конце маршрута турист совершил сплав по горной реке, и некоторые записи в дневнике смыло брызгами; кроме того, числа в записях могли исказиться. Теперь туристу интересно, какова могла быть максимальная высота, на которой он побывал за время похода. Помогите по имеющимся записям восстановить максимальную возможное значение максимальной высоты за время похода, либо определите, что записи исказились настолько, что не соответствуют никаким возможным значениям высот, удовлетворяющим ограничениям |h_i - h_i + 1| ≤ 1.