Jonglör
Bir sehrli jonglyorluq nömrəmin bir hissəsi olaraq, hazırda bir əlimlə dairəvi bir yolda bir sıra əşyaları jonglyor edirəm. Lakin, mürəkkəb nömrəm bitdikdə, bütün əşyaları müəyyən bir sırayla, minimum vaxtda yerə qoymaq istəyirəm. Hər bir hərəkətdə, ya bütün əşyaları bir sıra sola, ya da sağa döndərə bilərəm, ya da hazırda əlimdə olan əşyanı yerə qoya bilərəm. Əgər hazırda əlimdə olan əşyanı yerə qoysam, növbəti əşya (saat istiqamətində) əlimə düşəcək. Jonglyor etdiyim bütün topları yerə qoymaq üçün lazım olan minimum hərəkət sayını nə qədərdir?
Giriş verilənləri
Girişdə bir neçə test halı olacaq. Hər bir test halı, öz xəttində bir tam ədəd n (1 ≤ n ≤ 100000) ilə başlayır, jonglyor edilən topların ümumi sayını göstərir. Növbəti n sətirdən hər biri bir tam ədəd k_i (1 ≤ k_i ≤ n) ibarətdir, bu, bir topu təsvir edir: i jonglyorun əlindən saat istiqamətində başlayaraq topun mövqeyidir və k_i topun yerə qoyulma sırasıdır. {k_1, k_2, …, k_n} rəqəmlər dəsti 1..n rəqəmlərinin bir permutasiyası olacağına zəmanət verilir. Giriş bir xəttdə tək 0 ilə bitəcək.
Çıxış verilənləri
Hər bir test halı üçün, topların istənilən sırayla yerə qoyulması üçün lazım olan minimum hərəkət sayını göstərən bir tam ədəd çıxarın. Artıq boşluqlar çıxarmayın və cavabları boş sətirlərlə ayırmayın. Bütün mümkün girişlər cavabların imzalı 64-bit tam ədədə sığacağını təmin edir.
Nümunə girişin izahı: Birinci top jonglyorun əlindədir və üçüncü olaraq yerə qoyulmalıdır; ikinci top birinci topdan dərhal saat istiqamətindədir və ikinci olaraq yerə qoyulmalıdır; üçüncü top ikinci topdan dərhal saat istiqamətindədir və son olaraq yerə qoyulmalıdır.