e-olymp
Задачи

Сортировка сонных коров (Бронза)

Сортировка сонных коров (Бронза)

Фермер Джон пытается отсортировать своих n коров, пронумерованных 1 ... n, прежде чем они отправятся на пастбище завтракать.

В настоящее время коровы выстроены в линию и стоят в последовательности p1, p2, p3, ..., pn, а фермер Джон стоит перед коровой p1. Он хочет изменить порядок коров так, чтобы получить 1, 2, 3, ..., n, где корова 1 находится рядом с Фермером Джоном.

Коровы сегодня немного сонливы, поэтому в любой момент времени единственная корова, которая обращает внимание на инструкции фермера Джона, - это та, которая находится прямо напротив фермера Джона. За один шаг фермер Джон может проинструктировать эту корову двигаться k шагов вдоль линии для любого k в диапазоне 1 ... n - 1. k коров, мимо которых она пройдет, сдвинутся вперед, освобождая ей место, чтобы встать в ряд после них.

Например, предположим, что n = 4 и коровы стартуют в следующем порядке:

 FJ: 4, 3, 2, 1

Единственная корова, обращающая внимание на ФД, - это корова 4. Если он проинструктирует ее переместиться на 2 шага вперед, то порядок впоследствии будет выглядеть так:

 FJ: 3, 2, 4, 1

Теперь единственная корова, обращающая внимание на ФД, - это корова 3, поэтому на втором шаге он может дать инструкцию корове 3 и так далее, пока коровы не будут отсортированы.

Фермеру Джону не терпится завершить сортировку, чтобы вернуться домой на завтрак. Помогите ему найти минимальное количество шагов, необходимое для сортировки коров.

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

Первая строка содержит число n (1n100). Вторая строка содержит n целых чисел p1, p2, p3, ..., pn, указывающих на стартовый порядок коров.

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

Выведите одно целое число - минимальное количество шагов до того, как все n коров будут отсортированы. Известно, что фермер Джон действует оптимально.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
4
1 2 4 3
Выходные данные #1
3
Источник 2019 USACO Январь, Бронза