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

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

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

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

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

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

Input

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

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

Output

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

Examples