Тифани си купила нова и скапа игра (види слика). Играта бара многу размислување и се игра на следниот начин. Во почетна цевка, се пуштаат едно по друго N топчиња кои можат да бидат во една од три бои: црвена, жолта или зелена (ситуација лево на сликата). На крајот од таа цевка има 2 други цевки, лева и десна. Секое од топчиња од почетната цевка мора да се префрли (да продолжи) во една од следните 2 цевки. За секое топче, Тифани избира дали тоа ќе продолжи во левата или во десната цевка. Играта завршува кога сите топчиња ќе бидат префрлени во левата/десната цевка. Тогаш, во почетната цевка нема веќе топчиња, дел од топчињата се подредени во левата и дел во десната цевка (ситуација десно на сликата).

Согласно со распоредот на топчињата во цевките (левата и десната) се пресметуваат поени од играта. Да разгледаме едно топче. По правило, секое топче носи по 1 поен (*).
- Ако непосредно пред топчето има 2 топчиња од кои секое е во различна боја (т.е. тоа топче и двете пред него се во 3 различни бои) тогаш наместо 1 топчето носи 3 поена. (**)
- Инаку, ако непосредно пред топчето има 2 топчиња така што тоа топче и останатите 2 се во точно 2 различни бои тогаш наместо 1 топчето носи 2 поена. (***)
- Инаку, ако непосредно пред топчето има само едно топче кое е во различна боја од него тогаш наместо 1, топчето носи 2 поени. (****)
Збирот од поените од сите топчиња во двете цевки го дава вкупниот број поени.

На примерот даден на сликата, десно е дадено како топчињата се распоредени во двете цевки по крајот на играта (лево: RGRYYY, десно: R). За дадениот распоред на топчиња бодувањето е следно. Топчето означено со 1 носи 1 поен оти пред него нема други топчиња. Топчето 2 кое е зелено носи 2 поени бидејќи пред него има само едно топче (бр. 1) и тоа е во различна боја - црвена. Топчето 3 кое е црвено носи 2 поена бидејќи пред него се топчињата 1 и 2 и сите три се обоени во само 2 бои (црвена и зелена). Топчето 4 носи 3 поени бидејќи пред него се топчињата 2 и 3 и сите заедно се избоени во 3 различни бои (GRY). Топчето 5 носи 2 поени (RYY), а топчето 6 носи 1 поен (заедно со топчињата 5 и 4 пред него се избоени во една иста боја). Во десната цевка топчето 7 носи 1 поен. Вкупниот број на поени е 1+2+2+3+2+1+1=12.

Ако го знаете распоредот на топчињата во почетната цевка, пресметајте колку најмногу поени може да освои Тифани?

Влез

Во првиот ред е даден еден број N (1 ≤ N ≤ 100 000) кој го претставува бројот на топчиња. Во вториот ред има N знаци кои ги претставуваат боите на топчињата според редоследот на пуштање во почетната цевка:
‘R’ - црвено топче
‘Y’ - жолто топче
‘G’ - зелено топче


Забелешка:
За 30% од поените N ≤ 20.
За 25% од поените нема зелени топчиња.

Излез

Максималниот број на поени кои може да ги освои Тифани.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
6 
RYRGGY

излез
12

влез
7 
GGGGRRY

излез
11

Објаснување за првиот тест пример: Тифани може да освои најмногу 12 поени. Еден начин на кој може да освои најмногу поени е ако ги распредели топчињата на следниот начин: 1 - лево, 2 - лево, 3 - десно, 4 - десно, 5 - лево, 6 - десно. Во левата цевка најдолу ќе има црвено топче, над него жолто топче и над него зелено топче т.е. состојбата ќе е: RYG, а во десната:RGY. За првото топче Тифани добива 1 поен (R), за второто добива 2 поени (RY), за третото добива 1 поен (R), за четвртото добива 2 поени (RG), за 5-тoто добива 3 поени (RYG) и за 6-тото 3 поени (RGY).

Објаснување за вториот тест пример: Тифани може да освои најмногу 11 поени. Еден начин на кој може да освои најмногу поени е ако ги распредели топчињата на следниот начин: 1 - лево, 2 - лево, 3 - лево, 4 - десно, 5 - лево, 6 - десно, 7-десно . Во левата цевка состојбата ќе е: GGGR, а во десната: GRY. За првото топче Тифани добива 1 поен(G), за второто добива 1 поен (GG), за третото добива 1 поен (GGG), за четвртото добива 1 поен (G), за 5-тoто добива 2 поени (GGR), за 6-тото добива 2 поени (GR) и за 7-мото 3 поени (GRY).