Palindroms ir simetriska simbolu virkne, t.i., virkne, kas lasāma vienādi gan no kreisās puses uz labo, gan no labās puses uz kreiso. Jums jāuzraksta programma, kas dotai simbolu virknei nosaka, kāds mazākais simbolu skaits tajā jāiesprauž, lai pārveidotu to par palindromu.

Tā, piemēram, iespraužot divus simbolus virknē “Ab3bd”, to var pārveidot par palindromu (“dAb3bAd” vai “Adb3bdA”). Jāatzīmē, ka šajā gadījumā tas arī ir mazākais nepieciešamais iespraužamo simbolu skaits.

Ievaddatu pirmajā rindā ir dots naturāls skaitlis: ievada simbolu virknes garums N, 3<=N<=5000. Faila otrajā rindā dota simbolu virkne garumā N. Virkne var saturēt tikai latīņu alfabēta lielos ('A'..'Z') un mazos ('a'..'z') burtus un ciparus ('0'..'9'). Lielie un mazie burti tiek uzskatīti par atšķirīgiem simboliem.

Izvaddatu pirmajā rindā jāizvada viens vesels nenegatīvs skaitlis, kas ir mazākais virknē iespraužamo simbolu skaits.

Uzdevums izmantots 12. Vispasaules informātikas olimpiādē Pekinā (Ķīnas TR) 2000.gadā. 

Autors: Sergejs Meļņiks