Стіни

Обмеження: 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 в останній стінці.