ABB#9759
Fernando Vaterloo Universiteti tərəfindən yenicə başlanmış layihəni tamamlamaq üçün işə götürülmüşdür. Universitet kampus xaricində mühüm əcnəbi qonaqlar və əməkdaşlar üçün bunqalolardan ibarət nümayəndəlik küçəsi tikməyi planlaşdırır.
Hazırda küçə yalnız qismən tikilmişdir: o, göl sahilindən başlayır və meşəyə tərəf uzanaraq orada başa çatır. Fernandonun vəzifəsi küçənin sonunda, meşə tərəfdə, bir neçə yeni bunqalo tikməklə tikintini tamamlamaqdır. Artıq tikilmiş bütün evlər küçənin bir tərəfində yerləşir və yeni bunqalolar da eyni tərəfdə yerləşdirilməlidir. Mövcud bunqalolar tiplərinə görə fərqlənir və müxtəlif rənglərə boyanmışdır.
Fernandonun fikrincə, küçə bir qədər xaotik görünür. O, öz dizaynına əsasən tikiləcək yeni evlərin bu təəssüratı daha da gücləndirəcəyindən narahatdır. Qaydaya riayət etmək üçün o, yeni bunqalolara elə rənglər seçməyi qərara alıb ki, küçədəki evlərin bütün rəng ardıcıllığı simmetrik olsun. Bu o deməkdir ki, rənglərin ardıcıllığı küçənin hər iki ucundan oxunduqda eyni olmalıdır.
Digər məsələlərlə yanaşı, Fernandonu maraqlandıran sual budur: nəzərdə tutulan simmetriyaya uyğun olaraq layihəni tamamlamaq üçün neçə yeni bunqalo tikmək və müvafiq şəkildə rəngləmək lazımdır ki, bu say minimal olsun?
Birinci sətirdə n~(1 \le n \le 4 \cdot 10^5) — artıq tikilmiş bunqaloların sayını bildirən tam ədəd verilmişdir.
İkinci sətirdə onların rənglərinin küçənin gölə yaxın olan başlanğıcından etibarən ardıcıllığı verilmişdir. Bu, uzunluğu olan, hər biri müəyyən bir rəngi bildirən ''-dan ''-yə qədər kiçik latın hərflərindən ibarət sətirdir.
Bütün rəng ardıcıllığının simmetrik olması üçün küçənin sonuna əlavə edilməli və müvafiq şəkildə rənglənməli olan minimum bunqalo sayını çap edin.
Nümunə 1
Nümunə 2
Nümunə 3