Ежедневно диспетчеру железнодорожной станции "Москва-Сортировочная" приходится переставлять вагоны во многих поездах, чтобы они шли в заданном порядке. Для этого диспетчер может расцепить пришедший на станцию состав в произвольных местах и переставить образовавшиеся сцепки из одного или нескольких вагонов в произвольном порядке. Порядок вагонов в одной сцепке менять нельзя, также нельзя развернуть всю сцепку так, чтобы последний вагон в сцепке оказался первым в ней.
Диспетчер просит вашей помощи в определении того, какое минимальное число соединений между вагонами необходимо расцепить, чтобы переставить вагоны в составе в требуемом порядке.
Входные данные
В первой строке содержится целое число N, (1≤N≤100). Во второй
строке содержится перестановка натуральных чисел от 1 до N
(то есть все натуральные числа от 1 до N в некотором порядке).
Числа разделяются одним пробелом. Эта перестановка задает номера
вагонов в приходящем на станцию составе. Требуется, чтобы в уходящем
со станции составе вагоны шли в порядке их номеров.
Выходные данные
Программа должна записать единственное целое число, равное
минимальному количеству соединений между вагонами, которое нужно
расцепить в данном составе, чтобы их можно было переставить по порядку.
| Пример ввода | Пример вывода |
4 3 1 2 4 |
2 |
5 5 4 3 2 1 |
4 |
2 1 2 |
0 |