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 o(L1) şi o(L3), unde prin o(litera) înţelegem numărul de ordine al literei respective în alfabet (o(’a’)=1, o(’b’)=2, …, o(’z’)=26). Charlie aplică în mod repetat procedeul de eliminare şi calculează suma costurilor eliminărilor efectuate.

Cerinţă

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: 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.

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.

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ţă.
Î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ă.

Restricţii

• 3 ≤ numărul de litere ale şirului iniţial ≤ 100000

Exemple

charlie.in	charlie.out	Explicaţii
1 cadgfacbda	5	p = 1 Secvenţele alternante corect formate sunt: cad, facbd. Lungimea maximă este 5 Atenţie! Pentru acest test se rezolvă doar cerinţa a).
2 cbcabadbac	ccdc 21	p = 2 Şirul iniţial: cbcabadbac 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 Şirul rezultat în urma eliminării este: cbcabdbc 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 Şirul rezultat în urma eliminării este: cbcbdc 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 Şirul rezultat în urma eliminării este: ccdc Nu mai sunt posibile eliminări. Suma maximă obţinută este 21. Atenţie! Pentru acest test se rezolvă doar cerinţa b).

autor: Prof. Eugen Nodea

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com