== include(page="template/taskheader" task_id="charlie") ==

*_Charlie_* a decis să se joace cu literele dintr-un şir de caractere, şir ce conţine doar literele mici ale alfabetului englez ’a’…’z’. Jocul constă în a elimina litere din şir după următoarea regulă: fie L1, L2, L3 trei litere aflate pe poziţii consecutive în şir, atunci litera *L2* poate fi eliminată dacă şi numai dacă este strict mai mică lexicografic decât literele *L1* şi *L3*.
Pentru a face jocul mai interesant, *_Charlie_* ataşează eliminării literei *L2* un cost egal cu valoarea maximă dintre ō(L1) şi ō(L3), unde prin ō(litera) înţelegem numărul de ordine al literei respective în alfabet *(ō(’a’)=1, ō(’b’)=2,…,ō(’z’)=26)*. *_Charlie_* aplică în mod repetat procedeul de eliminare şi calculează suma costurilor eliminărilor efectuate.

*_Charlie_* a decis să se joace cu literele dintr-un şir de caractere, şir ce conţine doar literele mici ale alfabetului englez ’a’…’z’. Jocul constă în a elimina litere din şir după următoarea regulă: fie $L{~1~}$, $L{~2~}$, $L{~3~}$ trei litere aflate pe poziţii consecutive în şir, atunci litera *L{~2~}* poate fi eliminată dacă şi numai dacă este strict mai mică lexicografic decât literele *L{~1~}* şi *L{~3~}*.
Pentru a face jocul mai interesant, *_Charlie_* ataşează eliminării literei *L{~2~}* un cost egal cu valoarea maximă dintre $ō(L{~1~})$ şi $ō(L{~3~})$, unde prin $ō(litera)$ înţelegem numărul de ordine al literei respective în alfabet *(ō(’a’)=1, ō(’b’)=2,…,ō(’z’)=26)*. *_Charlie_* aplică în mod repetat procedeul de eliminare şi calculează suma costurilor eliminărilor efectuate.

h2. Cerinţe
Fiind dat un şir de caractere să se determine:

a) Lungimea maximă a unei secvenţe de litere alternante, adică o secvenţă pentru care literele aflate pe poziţii consecutive sunt de forma: *Li > Li+1 < Li+2 > Li+3 < Li+4 > … < Lj*.

a) Lungimea maximă a unei secvenţe de litere alternante, adică o secvenţă pentru care literele aflate pe poziţii consecutive sunt de forma: *L{~i~} > L{~i+1~} < L{~i+2~} > L{~i+3~} < L{~i+4~} > … < L{~j~}*.

b) Suma maximă pe care o poate obţine *_Charlie_* aplicând în mod repetat procedeul de eliminare a literelor, precum şi şirul obţinut în final.
h2. Date de intrare

Fişierul de intrare _charlie.in_ conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe următoarea linie se află un şir de caractere.

Fişierul de intrare _charlie.in_ conţine pe prima linie un număr natural $p$. Pentru toate testele de intrare, numărul p poate avea doar valoarea $1$ sau valoarea $2$. Pe următoarea linie se află un şir de caractere.

h2. Date de ieşire

*Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerinţă.*
În acest caz, în fişierul de ieşire _charlie.out_ se va scrie un singur număr natural L ce reprezintă lungimea maximă a unei secvenţe de litere alternante.
*Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerinţă.*

*Dacă valoarea lui $p$ este $1$, se va rezolva numai punctul a) din cerinţă.*
În acest caz, în fişierul de ieşire _charlie.out_ se va scrie un singur număr natural $L$ ce reprezintă lungimea maximă a unei secvenţe de litere alternante.
*Dacă valoarea lui $p$ este $2$, se va rezolva numai punctul b) din cerinţă.*

În acest caz, fişierul de ieşire _charlie.out_ va conţine două linii. Pe prima linie se va afla şirul rezultat în urma eliminărilor repetate de litere respectând regula enunţată, iar pe cea de-a doua linie suma maximă obţinută.
h2. Restricţii

* 3 ≤ numărul de litere ale şirului iniţial ≤ 100000
* Pentru rezolvarea corectă a primei cerinţe se acordă 25 de puncte, iar pentru cerinţa a doua se acordă 75 de puncte.
* Pentru 30% dintre teste numărul de litere ale şirului ≤ 1000

* $3$ ≤ numărul de litere ale şirului iniţial ≤ $100000$
* Pentru rezolvarea corectă a primei cerinţe se acordă $25$ de puncte, iar pentru cerinţa a doua se acordă $75$ de puncte.
* Pentru $30%$ dintre teste numărul de litere ale şirului ≤ $1000$

h2. Exemplu

h3. Explicaţie

În primul exemplu p = 1
Secvenţele alternante corect formate sunt: cad, facbd. Lungimea maximă este 5

În primul exemplu $p = 1$
Secvenţele alternante corect formate sunt: cad, facbd. Lungimea maximă este $5$

În al doilea exemplu p = 2

În al doilea exemplu $p = 2$

Şirul iniţial: cbcabadbac

Eliminăm din secvenţa bad litera a şi adăugăm la suma valoarea 4

Eliminăm din secvenţa bad litera a şi adăugăm la suma valoarea $4$

Şirul rezultat în urma eliminării este: cbcabdbac

Eliminăm din secvenţa bac litera a şi adăugăm la suma valoarea 3

Eliminăm din secvenţa bac litera a şi adăugăm la suma valoarea $3$

Şirul rezultat în urma eliminării este: cbcabdbc

Eliminăm din secvenţa dbc litera b şi adăugăm la suma valoarea 4

Eliminăm din secvenţa dbc litera b şi adăugăm la suma valoarea $4$

Şirul rezultat în urma eliminării este: cbcabdc

Eliminăm din secvenţa cab litera a şi adăugăm la suma valoarea 3

Eliminăm din secvenţa cab litera a şi adăugăm la suma valoarea $3$

Şirul rezultat în urma eliminării este: cbcbdc

Eliminăm din secvenţa cbd litera b şi adăugăm la suma valoarea 4

Eliminăm din secvenţa cbd litera b şi adăugăm la suma valoarea $4$

Şirul rezultat în urma eliminării este: cbcdc

Eliminăm din secvenţa cbc litera b şi adăugăm la suma valoarea 3

Eliminăm din secvenţa cbc litera b şi adăugăm la suma valoarea $3$

Şirul rezultat în urma eliminării este: ccdc

Nu mai sunt posibile eliminări. Suma maximă obţinută este 21.

Nu mai sunt posibile eliminări. Suma maximă obţinută este $21$.

== include(page="template/taskfooter" task_id="charlie") ==