Son döyüş

Böyük döyüş marslılar və insanlar arasında yaxınlaşır. İnsanların casusları müəyyən ediblər ki, marslıların n döyüşçüsü qalıb. Eyni zamanda, insanların da, marslılar kimi, tam olaraq n döyüşçüsü var.

Keçmiş döyüşlərin təcrübəsinə əsasən insanlar bilirlər ki, i-ci insan yalnız i nömrəli marslını məğlub edə bilər.

Komandir insanları sıraya düzmək qərarına gəldi. Marslıların planlarını öyrəndikdən sonra, komandir müəyyən etdi ki, sıradakı i-ci mövqedəki insan a[i] nömrəli marslı ilə döyüşəcək. İnsanlar yalnız hər bir döyüşçünün öz döyüşündə zəfər qazanacağı təqdirdə qalib gələcəklər.

Əvvəlcə komandir i-ci insanı sıranın i-ci mövqeyinə qoydu. Daha sonra o anladı ki, döyüşə az vaxt qalıb və əgər hər şeyi olduğu kimi buraxsa, insanlar məğlub ola bilərlər. Bir saniyə ərzində o, sıranın sonundakı insanı sıranın əvvəlinə keçirə bilər, bu əməliyyatdan sonra o, birinci mövqeyə keçir, qalan döyüşçülərin mövqe nömrəsi isə 1 artır.

Komandira kömək edin, sıranı minimum vaxtda elə yenidən qurmaq üçün ki, insanlar həlledici döyüşdə qalib gəlsinlər.

Giriş məlumatları

Birinci sətirdə hər iki tərəfin döyüşçülərinin sayı olan tam ədəd n verilir (1 ≤ n ≤ 2 * 10^5).

İkinci sətirdə n müxtəlif tam ədəd a[1]; a[2]; ...; a[n] verilir, burada a[i] sıranın i-ci mövqeyindəki insanın döyüşəcəyi marslının nömrəsidir (1 ≤ a[i] ≤ n, əgər i ̸= j, onda a[i] ̸= a[j] ).

Çıxış məlumatları

Yeganə ədəd k çıxarın — komandirin sıranı elə yenidən qurması üçün lazım olan minimum saniyə sayı ki, insanlar qalib gəlsinlər. Əgər marslıları məğlub etmək mümkün deyilsə, «-1» ədədini çıxarın.

Qeyd

Birinci nümunədə döyüşçülər əvvəlcə bir-birinə qarşı aşağıdakı kimi dururlar:

Marslılar: 1 4 2 3 5

İnsanlar: 1 2 3 4 5

İnsanlar məğlub olurlar, çünki 1 və 5 nömrəli marslılar öz döyüşlərini qazanırlar. İlk dəyişiklikdən sonra döyüşçülərin duruşu belə olur:

Marslılar: 1 4 2 3 5

İnsanlar: 5 1 2 3 4

İndi 2 və 3 nömrəli marslılar öz döyüşlərini qazanırlar, buna görə də daha bir dəyişiklik etmək lazımdır. Bundan sonra döyüşçülərin duruşu elə olur ki, bütün insanlar öz döyüşlərini qazanırlar.

Marslılar: 1 4 2 3 5

İnsanlar: 4 5 1 2 3