AlanashKO любить гроші. Напередодні Нового року йому подарували $N$ банкнот. Номінал кожної банкноти — додатне ціле число. Граючись, AlanashKO виклав усі банкноти в ряд і пронумерував їх зліва направо від $1$ до $N$. Потім він вирішив відсортувати всі банкноти в неспадному порядку. Для цього AlanashKO виконує таку процедуру: спочатку він розбиває банкноти на один або декілька підвідрізків, що не перетинаються, причому кожна банкнота належить якомусь підвідрізку. Далі всі підвідрізки по черзі зліва направо вставляються в новий ряд: спершу вставляється крайній лівий підвідрізок (перший підвідрізок), потім наступний зліва і так далі. Кожен підвідрізок вставляється або між будь-якими двома банкнотами, або на одному з двох кінців поточного нового ряду. Порядок банкнот усередині підвідрізка під час вставляння не змінюється.
AlanashKO хоче мінімізувати кількість підвідрізків так, щоб зрештою відсортувати банкноти в неспадному порядку. Допоможіть йому знайти цю величину.
Вхідні дані
Перший рядок містить одне додатне ціле число $N$ ($1 \le N \le 10^6$) — кількість банкнот. Наступний рядок містить $N$ додатних цілих чисел $a_i$ ($1 \le a_i \le 10^6$) — номінал $i$-ї банкноти.
Вихідні дані
В одному рядку виведіть одне ціле число — мінімальну кількість підвідрізків, яка дозволяє AlanashKO відсортувати банкноти.
Оцінювання
Ця задача містить чотири підзадачі:
- $N \le 8$. Оцінюється в 9 балів.
- $N \le 20$. Оцінюється в 16 балів.
- $N \le 300$. Оцінюється в 20 балів.
- $N \le 10^6$. Оцінюється в 55 балів.
Бали за кожну підзадачу нараховуються лише тоді, коли розв'язок успішно проходить усі попередні підзадачі.
Приклади
Вхідні дані 1
6 3 6 4 5 1 2
Вихідні дані 1
3
Примітка
Підвідрізок — це послідовність елементів, що йдуть підряд.
Розгляньмо приклад:
Мінімальна відповідь — розбиття на 3 підвідрізки: |3 6|4 5|1 2| (риски позначають межі підвідрізків).
Після першого кроку: початковий ряд — |4 5|1 2|, новий ряд — |3 6|.
На другому кроці підвідрізок |4 5| вставляється між $3$ і $6$.
Після другого кроку: початковий ряд — |1 2|, новий ряд — |3 4 5 6|.
Потім підвідрізок |1 2| вставляється на початок нового ряду, і отримуємо |1 2 3 4 5 6|.