n ячеек, в них лежат коробки с номерами от 1 до n - 1, а одна ячейка пустая. Состояние полки записано в массиве shelf длины n: shelf[i] — номер коробки в ячейке i, а 0 обозначает пустую ячейку. Каждое число от 0 до n - 1 встречается ровно один раз.
За один ход можно взять любую коробку и переложить её в пустую ячейку (место, где она лежала, становится пустым).
Полка считается упорядоченной, если номера коробок идут слева направо по возрастанию, а пустая ячейка стоит либо в самом начале, либо в самом конце. Например, при n = 4 подходят только [0, 1, 2, 3] и [1, 2, 3, 0].
Верните наименьшее число ходов, за которое полку можно упорядочить.shelf=[2, 0, 1, 3] → 2
Переставляем коробку 1 в пустую ячейку: [2, 1, 0, 3]. Затем коробку 2: [0, 1, 2, 3]. Двух ходов хватает, одним не обойтись.
shelf=[1, 2, 3, 0] → 0
Коробки уже идут по возрастанию, а пустая ячейка в конце — ходов не нужно.
shelf=[3, 1, 2, 0] → 1
Достаточно одного хода: коробка 3 переезжает в пустую последнюю ячейку, и получается [0, 1, 2, 3] — пустая ячейка теперь в начале.
shelf — перестановка чисел от 0 до len(shelf) - 1shelf=[2, 0, 1, 3]
2
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 164 теста на сервере, включая скрытые.