30286번 - Zvimbalius 다국어

Vytis turi naują žaislą – nuotoliniu būdu valdoma bepilotę skraidyklę, dar žinomą kaip dronas arba zvimbalius. Dronas yra bepilotis sragtasparnis, kuris skrenda vykdydamas jam duotas komandas.

Vyčio dronas supranta keturias komandas – S, P, R, V – kurios atitinkamai liepia jam skristi vieną metrą į šiaurę, pietus, rytus ar vakarus.

Vytis nusprendė išbandyti savo žaislą ir įvedė į jį N komandų, tačiau jas įvedęs suprato, kad dronas, įvykdęs tas komandas, gali nesugrįžti į pradinį tašką. Deja, komandas taisyti sunku, nes drono programinė įranga neleidžia nei pridėti, nei ištrinti jau įvestų komandų, o jas pakeisti galima tik po vieną. Vytis nori pakeisti kuo mažiau komandų taip, kad įvykdęs visas komandas dronas grįžtų į pradinį tašką.

Suskaičiuokite kiek mažiausiai komandų Vyčiui reikės pakeisti, kad dronas sugrįžtų į pradinį tašką.

Pirmoje eilutėje yra pateiktas skaičius N – įvestų komandų kiekis. Antroje eilutėje yra pateiktas N komandų eilutė be tarpų k₁k₂...k_N, kuriame k_i yra i-toji komanda, užkoduota taip, kaip nurodyta sąlygoje.

Išveskite vieną sveikąjį skaičių – kiek komandų reikia pakeisti, norint, kad dronas sugrįžtųį pradinį tašką.

Jei neįmanoma pakeisti komandų taip, kad dronas sugrįžtų į pradinį tašką, išveskite NEGALIMA.

• 1 ≤ N ≤ 100 000