20450번 - Расшифровка 서브태스크다국어

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

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

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