Козак Вус і гармата

Після того, як Козак Вус склав екзамен, він вирішив поїхати у печеру. Для того, щоб було веселіше, той вирішив використовувати гармати як транспортний засіб.

Шлях по печері має довжину $n$ метрів і він є поділеним на $n$ ділянок, довжиною $1$ метр кожна. Ділянки пронумеровані від $1$ до $n$ у порядку їх слідування від початку шляху до його кінця. Над кожною ділянкою на певній висоті висить сталактит (Сталактит — мінеральне утворення циліндричної або конусоподібної форми, яке звисає зі стель печер або інших порожнин, чи рукотворних споруд на кшталт мостів (з Вікіпедії).). Зокрема над першою ділянкою на висоті $a_1$, над другою на висоті $a_2$, ..., над $n$-ою ділянкою на висоті $a_n$. На умовній $n+1$ ділянці (тобто після шляху) стоїть стіна, яка займає увесь простір з землі до стелі (тобто усю вертикальну лінію).

На кожній з ділянок, окрім останньої, він поставив по гарматі на висоті $0$. Кожна з них напрямлена вгору під кутом $45$ градусів. Далі Козак Вус сідає у першу гармату і стріляє. Він летить під кутом $45$ градусів вперед допоки не вріжеться в сталактит. Потім він падає вертикально вниз. Зверніть увагу, що навіть якщо Козак доторкається до кута сталактита (друга ділянка на малюнку), то він пролітає далі, тобто не падає. Нехай він упав на $i$-тому відрізку. Якщо $i$ "— останній відрізок (тобто, $i=n$), то на цьому його розваги закінчуються. Інакше, він стрибає у гармату на $i$-тому відрізку і знову стріляє собою. Цей процес повторюється до тих пір, поки Козак не потрапить на $n$-ий відрізок.

Ілюстрація до першого прикладу (червоним позначено політ після пострілу, синім "— падіння після удару об сталактит)

Скільки разів доведеться вистрілити собою Козаку Вусу?

Вхідні дані

Перший рядок містить одне ціле число $n$ ($1\le n\le 2\cdot 10^5$) "— довжина шляху.

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($2\le a_i\le 10^9$) "— висоти, на яких знаходяться сталактити на відрізках.

Вихідні дані

Виведіть єдине число "— кількість пострілів, яку доведеться виконати Козаку Вусу.

Приклади