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

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

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

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

Рассмотрим на примере. При $N$ = $5$ изначальная линия бегунов выглядит так: $1$ $2$ $3$ $4$ $5$. В процессе у участника с номером $2$ развязываются шнурки. Пока он их завязывает, предположим, что двоим участникам удается его обогнать. Тогда порядок участников становится: $1$ $3$ $4$ $2$ $5$. Если теперь у бегуна с номером $4$ возникнут проблемы со шнурками, из-за чего он пропустит, например, одного человека вперед, то линия станет: $1$ $3$ $2$ $4$ $5$.

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

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

В первой строке находится одно целое число $N$($1$ $\le$ $N$ $\le$ $200000$).

Во второй строке находятся $N$ целых чисел $p_1$, $p_2$, $\ldots$, $p_N$($1$ $\le$ $p_i$ $\le$ $N$, $p_i$ $\neq$ $p_j$ если $i$ $\neq$ $j$) — первым финишировал бегун $p_1$, вторым был $p_2$, ..., последним — $p_N$.

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

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

Примеры

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

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