Руйнування будівель
У Баку є будівлі, які потребують знесення. На їхньому місці планується зведення нових споруд. Для цього необхідно зруйнувати старі будівлі.
Бариш — фахівець з демонтажу будівель. У нього є супер-робот, здатний знищувати будівлі.
У місті розташовано n будівель, які стоять поруч одна з одною. Щоб знести їх, Бариш використовує свого робота.
Кожна будівля складається з блоків, розташованих один над одним. Робот повинен зруйнувати всі ці блоки. За один хід робот може знищити всі зовнішні блоки. Виходячи з цього, обчисліть, скільки ходів знадобиться роботу, щоб зруйнувати всі будівлі.
Блок вважається зовнішнім, якщо хоча б з одного з його 4 напрямків (вліво, вправо, вниз, вгору) є порожнє місце (для наочності дивіться на картинку).
Вхідні дані
У першому рядку задано кількість будівель n (1 ≤ n ≤ 10^5). У наступному рядку наведено висоти будівель h[1], h[2], ..., h[n] (1 ≤ h[i] ≤ 10^9).
Вихідні дані
Виведіть одне ціле число — кількість ходів, необхідних для руйнування всіх будівель.
Ілюстрація до першого прикладу
