Стіни

Обмеження: 2 сек., 256 МіБ

Зеник з Марічкою підійшли до закинутої будівлі, в якій збереглось лише $n$ стін, розташованих одна за одною. Висота $i$-ої стіни рівна $h_i$.

Зеник дуже любить лазити по стінах, разом з тим Марічка вирішила зачекати його. Дівчина чекає його за останньою стіною. Зеник хоче, щоб з кожної стіни йому було видно Марічку. Для цього він може робити дірки в стінах.

Для того, щоб з $i$-ої стіни Зеник міг бачити Марічку йому потрібно, щоб існувала така висота $y \in [0, h_i]$, що для будь-якої стіни $j>i$ або $h_j \le y$ або в цій стіні на висоті $y$ є дірка. Значення $y$ може бути не цілим. Також зауважте, що якщо висота якоїсь стінки рівна $y$, то Зеник може бачити через цю стінку і додаткової дірки робити не потрібно. Зенику цікаво, яку мінімальну кількість дірок йому потрібно зробити, щоб бачити Марічку з кожної стіни.

Вхідні дані

У першому рядку задано єдине ціле число $n$.

У другому рядку задано $n$ цілих чисел $h_i$ — висоти стін.

Вихідні дані

Виведіть єдине число — мінімальну необхідну кількість дірок.

Обмеження

$1 \le n \le 2 \cdot 10^5$,

$1 \le h_i \le 10^9$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 9 9 5 2 1 3 7	3

Примітки

У прикладі можна зробити 3 дірки: дірку на висоті 1 у двох останніх стінках та на висоті 4.7 в останній стінці.