Вам дається \(n\) кубиків у певному порядку, і ваше завдання — побудувати з них вежі. Щоразу, коли два кубики лежать один на одному, верхній куб має бути меншим за нижній.

Ви повинні обробляти кубики в заданому порядку. Ви завжди можете або розмістити куб на вершині існуючої вежі, або почати будувати нову вежу. Яка мінімально можлива кількість веж?

Обмеження

• \(1≤n≤2⋅10^5\)
• \(1≤k_i ​ ≤10^9\)

Формат вхідних даних

Перший рядок містить ціле число \(n\): кількість кубиків.

Наступний рядок містить \(n\) цілих чисел \(k_1 ​,k_2 ​ ,…,k_n\) ​ : розміри кубів.

Формат вихідних даних

Вивести одне ціле число: мінімальна кількість веж.

Приклад вхідних даних

5
3 8 2 1 5

Приклад вихідних даних

2