Знесення будівель#9029
У Баку є будівлі, які потребують знесення. На їхньому місці планується зведення нових споруд. Для цього необхідно знести старі будівлі.
Олег — фахівець зі знесення будівель. У нього є супер-робот, здатний знищувати будівлі.
У місті розташовано будівель, які стоять поруч одна з одною. Щоб знести їх, Олег використовує свого робота.
Кожна будівля складається з блоків, розташованих один над одним. Робот повинен знести всі ці блоки. За один хід робот може знищити всі зовнішні блоки. Виходячи з цього, обчисліть, скільки ходів знадобиться роботу, щоб знести всі будівлі.
Блок вважається зовнішнім, якщо хоча б з одного з його напрямків (вліво, вправо, вниз, вгору) є порожнє місце (для наочності дивіться на картинку).
У першому рядку задано кількість будівель (1 \leq n \leq 10^5). У наступному рядку наведено висоти будівель h_1, h_2, \ldots, h_n (1 \leq h_i \leq 10^9).
Виведіть одне ціле число — кількість ходів, необхідних для знесення всіх будівель.
Приклад 1
Приклад 2
Ілюстрація до першого прикладу:
