Известно, что если сохранить в каждом слове текста первую и последнюю букву, а остальные переставить произвольным образом, получившийся текст по-прежнему можно достаточно свободно прочитать. В лаборатории информатики исследуют аналогичный феномен для числовых последовательностей.

Будем называть последовательность, состоящую из целых положительных чисел, корректной, если первое число в этой последовательности является минимальным, а последнее — максимальным. Например, последовательности $$$[1, 3, 2, 4]$$$ и $$$[1, 2, 1, 2]$$$ являются корректными, а последовательность $$$[1, 3, 2]$$$ — нет.

Задана последовательность $$$[a_1, a_2, \ldots, a_n]$$$. Будем называть отрезок элементов заданной последовательности $$$[a_l, a_{l+1}, \ldots, a_r]$$$ корректным, если он представляет собой корректную последовательность: $$$a_l$$$ является минимальным числом на этом отрезке, а $$$a_r$$$ — максимальным.

В рамках исследования необходимо разбить заданную последовательность на минимальное количество непересекающихся корректных отрезков. Например, последовательность $$$[2, 3, 1, 1, 5, 1]$$$ можно разбить на три корректных отрезка: $$$[2, 3]$$$ и $$$[1, 1, 5]$$$ и $$$[1]$$$.

Требуется написать программу, которая по заданной последовательности определяет, на какое минимальное количество корректных отрезков её можно разбить.

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Подзадача} & \text{Баллы} & \text{Ограничения} & \text{Необх. подзадачи} \\ \hline 1 & 30 & n \le 500 & 0 \\ \hline 2 & 30 & n \le 5\,000 & 0, 1 \\ \hline 3 & 40 & n \le 300\,000 & 0, 1, 2 \\ \hline \end{array}$$$$$$

Вам будут начислены баллы за группу, только если пройдены все тесты этой группы и во всех группах, от которых она зависит. Группа $$$0$$$ соответствует примерам из условия.