Расшифровка

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

Будем называть последовательность, состоящую из целых положительных чисел, корректной, если первое число в этой последовательности является минимальным, а последнее --- максимальным. Например, последовательности $\[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]$.

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

Первая строка входных данных содержит целое число $n$ ($1 \le n \le 300\\,000$) --- количество элементов в заданной последовательности.

Вторая строка содержит $n$ целых чисел $a\_1, a\_2, \ldots, a\_n$ --- заданную последовательность ($1 \le a\_i \le 10^9$).

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