Seifa atslēgas mehānisms sastāv no N vienādiem diskiem, kas sadalīti 10000000 vienādos sektoros, kuri sanumurēti ar naturāliem skaitļiem no 1 līdz 10000000 pēc kārtas pulksteņrādītāja virzienā.
Diski ir izvietoti uz kopīgas ass viens virs otra. Sākumā visi diski ir pagriezti tā, ka sektori ar vienādiem numuriem atrodas tieši viens virs otra.
Katram diskam viens sektors ir izgriezts, kuru sauc par caurumu. Lai seifu atvērtu, diski ir jāpagriež tā, lai visi caurumi atrastos viens virs otra.
Katru disku vienā sekundē var pagriezt par vienu sektoru vienā virzienā (pulksteņa vai pretēji pulksteņa rādītāja virzienam).
Uzrakstiet programmu, kas nosaka mazāko laiku, kāds nepieciešams seifa atvēršanai!
Teksta faila safe.in pirmajā rindā dota naturāla skaitļa N(disku skaits, 2 ≤N≤100000) vērtība.
Katrā no nākošajām N rindām dots pa vienam naturālam skaitlim - tā sektora, kurš ir caurums, numuram.
Faila i+1-ajā rindā ir skaitlis Pi, 1≤Pi ≤1000000, ja i-tajā diskā caurums ir sektorā Pi.
Teksta faila safe.out vienīgajā rindā jāizvada seifa atvēršanai mazākais nepieciešamais laiks sekundēs.
Piezīme: Pievērsiet uzmanību šī skaitļa iespējamajai vērtībai!
| safe.in | safe.out |
3 5 17 7 |
12 |
| safe.in | safe.out |
4 9999999 7 16 9999995 |
29 |
| safe.in | safe.out |
4 1 2500001 5000000 7500002 |
9999998 |