Районная олимпиада по информатике 2022 года за 9 класс | Казахстанские олимпиады

Задача C. Разделяй и сортируй

Вам дан массив $a$ из $n$ целых чисел. Подотрезком будем называть последовательность из одного и более подряд идущих элементов массива

Нархан решил отсортировать массив в порядке неубывания. Для этого Нархан поступает следующим образом: сперва он делит весь массив на один или несколько непересекающихся подотрезков так, чтобы каждое число находилась в каком-либо подотрезке. Далее Нархан сортирует числа внутри каждого подотрезка.

Нархан хочет максимизировать количество подотрезков так, чтобы массив $a$ в итоге был отсортирован. Помогите ему найти это значение.

Формат входного файла

В первой строке входных данных дается целое положительное число $n (1 \leq n \leq 10^5)$ — длина массива.

Во второй строке входных данных дается $n$ целых положительных чисел $a_i (1 \leq a_i \leq 10^9)$.

Формат выходного файла

В единственной строке выходных данных выведите одно число — максимальное количество подотрезков, при котором Нархан способен отсортировать массив.

Примеры

Ввод

7
3 1 2 5 4 6 5

Вывод

3

Ввод

15
2 2 5 4 3 6 18 8 18 15 18 18 18 19 26

Вывод

10