Стіни

Limits: 2 sec., 256 MiB

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

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

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

Input

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

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

Output

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

Constraints

\(1 \le n \le 2 \cdot 10^5\),

\(1 \le h_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 9 9 5 2 1 3 7	3

Notes

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