Ваня решил навести порядок в книжном шкафу. У него есть полное собрание детской энциклопедии – 16 томов, каждый том имеет свой номер. Сейчас они расставлены на полке шкафа в следующем порядке:
5 3 13 10 11 16 6 14 4 12 2 1 7 15 8 9
Ваня хочет расставить их по возрастанию номера тома. При этом он не хочет снимать с полки больше одной книги за раз. Перестановку книг он выполняет по следующему алгоритму:
1. Выбрать одну книгу и снять ее с полки
2. Вставить вынутую книгу между двумя другими книгами на этой же полке (книги легко двигаются по полке влевовправо, между двумя книгами можно последовательно вставить сколько угодно книг)
При необходимости повторить шаги 1-2.
При этом во время уборки Ваня хочет снимать с полки наименьшее возможное число книг. Какое наименьшее возможное число книг ему придется вынуть и потом поставить на полку в другое место, чтобы расставить книги по порядку?
Пример:
Если нужно правильно расставить 4 книги, изначально расположенные в следующем порядке: 1 4 3 2, Ваня может привести полку в порядок, переставив две книги, например:
1) вынуть второй том и поставить его между первым и четвертым (получится 1 2 4 3)
2) вынуть третий том и поставить его между вторым и четвертым (получится 1 2 3 4). В ответ в данном случае записывается «2» - так как с полки снималось две книги.