Сортировка вручную
Пришло время расставить книжки на полке. На ней стоят n книг, однозначно пронумерованных целыми числами от 1 до n. Требуется расставить их в порядке возрастания номеров. Вы прекрасно знаете, что быстрая сортировка и сортировка вставками — быстрые методы сортировки, однако их непросто исполнять вручную. Они эффективны для компьютеров, а не для людей.
Поэтому вы решили сортировать книги, вставляя i-ю книгу на i-ю позицию. Сколько операций вам придётся выполнить для успешной сортировки? Вот два примера операции:
1 3 4 5 2 => 1 2 3 4 5, если мы вставляем 2 на свое место.
1 3 4 5 2 => 1 4 3 5 2, если мы вставляем 3 на свое место.
Входные данные
В первой строке входного файла содержится целое число n (1 ≤ n ≤ 20) — количество книг на полке.
Во второй строке записано n различных целых чисел от 1 до n — номера книг в том порядке, в котором они расставлены вначале.
Выходные данные
Выведите единственное целое число — минимальное количество операций указанного вида, которое придётся выполнить для сортировки.