Фермер Джон пытается отсортировать свои \(N\) коров (\(1 \leq N \leq 100\)),
последовательно пронумерованных \(1 \dots N\).
В настоящий момент коровы выстроились в линию в порядке
\(p_1, p_2, p_3, \dots, p_N\), и ФД стоит перед коровой \(p_1\).
Он хочет переупорядочить коров так, чтобы они стали в порядке
\(1, 2, 3, \dots, N\), с коровой \(1\) перед ФД.
Фермера Джона слышит только корова, которая стоит перед ним.
В этот момент ФД может сказать ей перейти на \(k\) позиций назад
(\(k\) в интервале \(1 \ldots N-1\).). \(k\) коров, которых она проходит ,
двигаются вперёд, освобождая место для неё, в которое она и
становится.
Например, пусть \(N=4\) и коровы стоят в таком порядке
ФД: 4, 3, 2, 1
Единственная корова, которая слышит ФД, это корова \(4\).
Если он скажет ей сдвинуться на 2 позиции, порядок станет таким:
ФД: 3, 2, 4, 1
Теперь ФД слышит только корова \(3\). Теперь ей можно давать инструкцию и т.д.
Определите минимальное количество инструкций, которые должен дать ФД,
чтобы отсортировать всех коров.
ФОРМАТ ВВОДА (файл sleepy.in):
Первая строка ввода содержит
\(N\).
Вторая строка ввода содержит \(N\) разделённых пробелом целых чисел,
\(p_1, p_2, p_3, \dots, p_N\), указывающих начальное размещение коров.
ФОРМАТ ВЫВОДА (файл sleepy.out):
Одно целое число - минимальное количество команд, которые должен дать ФД
чтобы отсортировать всех коров.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2 4 3
|
3
|