Kazak Vus və leksikoqrafiya#10358
Kozaka yaxınlarda tam ədəddən ibarət massivini hədiyyə etdilər.
Vus dərhal bu massiv elementlərini elə sıralamaq istədi ki, hər hansı qonşu ədədlər fərqli olsun. Bütün belə sıralamalar arasında o, leksikoqrafik olaraq ən kiçiyini tapmaq istəyir.
Xatırladaq ki, leksikoqrafik qayda belə təyin olunur: Gəlin iki massivimiz olsun. İki massivdə fərqli olan ilk mövqeni tapaq. Əgər bu mövqedə birinci massivdəki element ikinci massivdəki elementdən kiçikdirsə, onda birinci massiv leksikoqrafik olaraq ikinci massivdən kiçikdir, əks halda birinci massiv ikinci massivdən böyükdür. Məsələn, aşağıdakı bərabərsizliklər doğrudur: [10, 3, 1] < [10, 4, 5], [1, 1, 1] < [1, 2, 3], [1, 2, 3] < [10, 10, 10].
Birinci sətir massiv elementlərinin sayı olan (1 \leq n \leq 5 \cdot 10^5) tam ədədini ehtiva edir.
İkinci sətir tam ədəd a_1, a_2, ..., a_n (1 \leq a_i \leq 5 \cdot 10^5) massiv elementlərini ehtiva edir.
Əgər Vusun massivini sıralamaq mümkün deyilsə, tək ədəd çıxarın.
Əks halda, tam ədəd çıxarın — Vusun massivinin leksikoqrafik olaraq minimal sıralanması.
Nümunə 1
Nümunə 2
Nümunə 3
Birinci nümunədə yeganə sıralama mövcuddur.
İkinci nümunədə başqa sıralamalar da mövcuddur, məsələn: [1, 2, 3, 4, 1, 2] və ya [1, 4, 1, 2, 3, 2]. Amma bütün bu sıralamalar leksikoqrafik olaraq [1, 2, 1, 2, 3, 4]-dən böyükdür.
Üçüncü nümunədə düzgün sıralama mövcud deyil (massivdə həmişə qonşu mövqelərdə iki birlik olacaq).
Bu məsələdə test sonrası qiymətləndirmə istifadə olunur. Bəzi əlavə məhdudiyyətlər:
( bal): n \leq 10^3, a_i \leq 2
( bal): n \leq 10^3, a_i \leq 3
( bal): n \leq 10^3, a_i \leq 5 \cdot 10^5
( bal): n \leq 5 \cdot 10^5, a_i \leq 2
( bal): n \leq 5 \cdot 10^5, a_i \leq 3
( bal): n \leq 5 \cdot 10^5, a_i \leq 5 \cdot 10^5