Вам дається ~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