Ribbons
Турнир за Купата на Декана, 2010
Time Limit: 0.1s, Memory Limit: 64MiB
Най-шокиращо за Ели, нейната приятелка Крис започна работа. И то не нещо промотерка, ала бала, ами в магазин за подаръци! Ужас!

Ели още на следващия ден отиде при нея за да изрази съчувствието си (добре де, да позлорадства). В този момент Кристина изрязваше панделки от дълъг лист с цветни ивици. На листа имаше N ивици, всяка от които широка по един сантиметър и оцветена в червено, зелено или синьо. Оказа се, че шефката на Крис ѝ е наредила да изреже възможно най-много цветни панделки от дадения лист, без да изхвърля никаква част от него. Една панделка може да бъде с ширина два или три сантиметра, като има допълнително изискване един от цветовете да се среща поне два пъти. Така, ако панделката е с ширина две, тя трябва да е едноцветна, а ако е с ширина три, може да съдържа максимум два различни цвята).

Крис обаче нямаше никаква идея как точно да нареже листа, така че да изпълни условията на шефката! Ели хвърли един бърз поглед, извади лаптопа си и седна да коди. След не повече от пет минути тя беше готова с програма, която да изчисли колко най-много панделки може да се направят от дадения лист, или да казва, че това е невъзможно. От вас се иска да напишете сходна програма.
Вход
На първия ред на стандартния вход ще бъде зададено цялото число N, указващо от колко ленти се състои цветният лист. На втория ред ще има стринг с дължина N, съставен от буквите 'R', 'G', и 'B', указващи, съответно, червена, зелена, или синя ивица. Този стринг задава цветовете на лентите, в реда, в който са подредени на цветния лист.
Изход
На единствен ред на стандартния изход изведете едно цяло число – колко най-много панделки могат да се направят без да се изхвърля нищо от листа, или -1, ако по никакъв начин листът не може да бъде нарязан на валидни панделки.
Ограничения
  • 1 ≤ N ≤ 100,000
Примерен Вход Примерен Изход
25 BBRGBGGGGRBBGGRRBBGRGGRBB 9
4 RGRG -1
33 RGRGGGGRGRRRGRGRGGRRGGRRBGBBGBBGG 13
В първия пример едно от валидните разбивания е {BBR, GBG, GGG, RBB, GG, RR, BBG, RGG, RBB}, което дава 9 панделки. Вторият пример е невъзможен, тъй като ако вземем RGR ще трябва да изхвърлим оставащото G, а това е забранено.
Мрън!