Областная олимпиада по информатике 2022 года за 10 класс | Казахстанские олимпиады

Задача A. Спортивные программисты

Ограничение по времени Ограничение по памяти
1 секунда 256 мегабайт

Ассоциация спортивных программистов Казахстана решила организовать забег перед Олимпиадой. В забеге приняло участие NN человек. На старте бегуны расположились друг за другом в линию в порядке от 11 до NN.

Когда был дан свисток, участники забега ринулись с мест, при этом поддерживая порядок кто за кем бежит. Участник с номером 11 бежит первым, а участник с номером NN — последним. Но какой же это забег, если никто никого не обгоняет? Обгон происходит, когда у одного из участников развязываются шнурки на кроссовках. Пока бегун завязывает свои шнурки, следующие за ним участники могут его обогнать.

Рассмотрим на примере. При NN = 55 изначальная линия бегунов выглядит так: 11 22 33 44 55. В процессе у участника с номером 22 развязываются шнурки. Пока он их завязывает, предположим, что двоим участникам удается его обогнать. Тогда порядок участников становится: 11 33 44 22 55. Если теперь у бегуна с номером 44 возникнут проблемы со шнурками, из-за чего он пропустит, например, одного человека вперед, то линия станет: 11 33 22 44 55.

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

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

В первой строке находится одно целое число NN(11 \le NN \le 200000200000).

Во второй строке находятся NN целых чисел p1p_1, p2p_2, \ldots, pNp_N(11 \le pip_i \le NN, pip_i \neq pjp_j если ii \neq jj) — первым финишировал бегун p1p_1, вторым был p2p_2, ..., последним — pNp_N.

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

Выведите одно целое число — ответ на задачу.

Примеры

Входные данные

Выходные данные

Решение

Здесь могут быть решения задач с LaTeX\LaTeX