== 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 $L{~1~}$, $L{~2~}$, $L{~3~}$ 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 *L{~1~}* şi *L{~3~}*.

*_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

* $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

* Pentru 30% dintre teste numărul de litere ale şirului ≤ $1000$

h2. Exemplu