4. Ohromná estetickosť

Odjakživa to tak bolo… V kadiach pred Tesclandom kapre, na cestách čľapkanica, v izbe predčasne vybrakovaný adventný kalendár. V obývačke stromček, na ňom obaly od salóniek, z toho polovica prázdna. Prázdniny sa už nezadržateľne blížia, no Matúš ešte musí dokončiť ten projekt z dejepisu o prínose Etruskov pre Staroveký Rím.

Dejepis je super, ale v tomto predvianočnom čase naň už niet dostatok síl. Na druhej strane, v Tesclande sa momentálne chystá zaujímavá akcia. Každých \(15\) minút, dostanú všetci zákazníci prítomní v predajni vianočnú guľu. Vianočné gule sú dostupné v \(20\) farbách, no zákazník si farbu nevyberá. Našťastie, je dopredu známe, kedy sa budú rozdávať ktoré farby.

Matúš sa tak rozhodol, že nudu plynúcu z písania domácich úloh nahradí niečim užitočnejším a pôjde do Tesclandu nazbierať nejaké gule. Nechce ale ľubovoľné farby… Rád by vyzbieral čo najviac gúľ takých, že ak ich potom všetky zavesí nad svoj písací stôl, postupnosť ich farieb bude rovnaká z ľavej aj z pravej strany.

Samozrejme, nepôjde tam len-tak hocikedy, keďže tie domáce úlohy naozaj musí niekedy dokončiť a nemôže teraz všetko svoj čas stráviť v obchode (aj keď rád by). Chcel by tam stráviť čo najmenej času a nechce tam ísť viac ako raz. Inými slovami, pôjde tam raz, strávi tam určitý čas, počas ktorého dostane nejaké vianočné gule (a žiadnu neodmietne), a potom sa vráti domov.

Matúš tam naozaj chce ísť. Pomôžte mu vopred zistiť, koľko najviac gúľ si domov prinesie, aby neporušil dané pravidlá.

Úloha

Poznáte postupnosť farieb vianočných gúľ v poradí, v akom sa budú rozdávať. Zistite, koľko najviac si ich Matúš môže priniesť domov, ak chce v obchode stráviť iba jeden súvislý časový úsek a chce, aby množina týchto gúľ spĺňala zaujímavú ohromne estetickú podmienku: Všetky získané gule musí byť možné zavesiť vedľa seba tak, aby vzniknutá postupnosť ich farieb bola rovnaká z ľavej aj z pravej strany. (Vianočné gule môžu byť zavesené v inom poradí, v akom boli rozdávané v obchode)

Formát vstupu

Na prvom riadku vstupu sa nachádza \(1 \leq n \leq 300\,000\) udávajúce počet rozdávaní vianočných gúľ v obchode (Pri jednom rozdávaní, získa každý človek v supermarkete vianočnú guľu).

Na druhom riadku vstupu sa nachádza \(n\) farieb gúľ v poradí, v akom budú rozdávané, pričom farba gule je vyjadrená malým písmenom anglickej abecedy od a po t.

Formát výstupu

Na výstup vypíšte jedno číslo, dĺžku najdlhšej súvislej podpostupnosti získaných gúľ, ktorej preusporiadaním (alebo aj ponechaním v pôvodnom poradí) môže vzniknuť postupnosť spĺňajúca podmienku o ohromnej estetickosti.

Príklady

Input:

12
aabbccddabcd

Output:

9

Ak bude Matúš v obchode od prvej po deviatu (vrátane) štvrťhodinu, vyzbiera vianočné gule týchto farieb: aabbccdda. Tieto vieme zavesiť nad písací stôl, napríklad, v takomto poradí: dcbaaabcd, čo je palindróm, a teda táto súvislá podpostupnosť vianočných gúľ spĺňa Matúšove nekompromisné podmienky. Z pohľadu voľným okom je jasné, že táto podpostupnosť má dĺžku 9 a je najdlhšia možná.

Input:

20
ghjahjghsajdjhlfslja

Output:

7