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