Жонглёр
В рамках моего магического жонглирования я жонглирую несколькими объектами по круговой траектории одной рукой. Когда мое сложное выступление заканчивается, я хочу уронить все объекты в определенном порядке за минимальное количество времени. За один ход я могу либо повернуть все объекты против часовой стрелки на одну позицию, по часовой стрелке на одну позицию, либо уронить объект, который находится в моей руке. Если я уроню объект, следующий по часовой стрелке объект окажется в моей руке. Какое минимальное количество ходов требуется, чтобы уронить все шары, которыми я жонглирую?
Входные данные
Входные данные содержат несколько тестов. Каждый тест начинается с целого числа n (1 ≤ n ≤ 100000) на отдельной строке, указывающего общее количество шаров, которыми жонглируют. Каждая из следующих n строк содержит одно целое число k_i (1 ≤ k_i ≤ n), которое описывает один шар: i — это позиция шара, начиная по часовой стрелке от руки жонглера, а k_i — это порядок, в котором шар должен быть уронен. Набор чисел {k_1, k_2, …, k_n} гарантированно является перестановкой чисел 1..n. Ввод заканчивается строкой, содержащей единственный 0.
Выходные данные
Для каждого теста выведите одно целое число на отдельной строке, указывающее минимальное количество ходов, необходимых, чтобы уронить все шары в заданном порядке. Не выводите лишние пробелы и не разделяйте ответы пустыми строками. Все возможные входные данные дают ответы, которые поместятся в знаковое целое число 64-бит.
Объяснение примера ввода: Первый шар находится в руке жонглера и должен быть уронен третьим; второй шар находится сразу по часовой стрелке от первого шара и должен быть уронен вторым; третий шар находится сразу по часовой стрелке от второго шара и должен быть уронен последним.