== include(page="template/taskheader" task_id="weeee") ==
Poveste şi cerinţă...
Micutul B urmeaza sa spuna primul sau cuvant. Mama lui tot repeta "Hai B, stiu ca primul tau cuvant va fi mami". Tatal lui B crede ca primul cuvant spus de acesta va fi "Tati". Cand in sfarsit B vorbeste, el spune doar atat: WEEEEEEEEEEE. Ambii parinti sunt dezamagiti de el, asa ca decid sa nu mai vorbeasca cu el. Suparat, B se duce la locul sau de joaca.
El are cuburi pe care scrie cate o litera. Suparat, el arunca toate cuburile pe care sunt inscriptionate alte litere in afara de W si E. Apoi, aseaza cuburile in linie. Scopul jocului sau este sa formeze un cuvant cat mai lung din cuburile ramase (cele care contin literele W sau E). Din pacate, el stie numai un cuvant: un cuvant care incepe cu litera W si apoi este format numai din E-uri. El vrea sa formeze cuvantul cu lungimea maxima posibila. Astfel, scopul sau este sa formeze o subsecventa a cuburilor care incepe cu W si care contine apoi toti E-ii din cuburi.
Singura operatie admisa a jocului sau este sa aleaga 2 cuburi adiacente si sa le interschimbe. Gasiti numarul minim de interschimbari astfel incat sa existe o subsecventa a cuburilor care sa inceapa cu W si sa contina apoi toti E-ii, sau micutul B va incepe sa planga :(
h2. Date de intrare
Fişierul de intrare $weeee.in$ ...
Fişierul de intrare $weeee.in$ va contine pe prima linie numarul N, reprezentand lungimea sirului de cuburi. A doua linie a fisierului contine sirul de cuburi, privit de la stanga la dreapta. Pentru fiecare dintre cele N cuburi va fi scrisa litera W sau E, corespunzatoare literei inscriptionate pe cubul respectiv.
h2. Date de ieşire
În fişierul de ieşire $weeee.out$ ...
În fişierul de ieşire $weeee.out$ se va afisa un singur numar, reprezentand numarul minim de interschimbari astfel incat sa existe o subsecventa care sa inceapa cu W si sa contina apoi toti E-ii sirului initial. Pentru ca o subsecventa sa fie un cuvant valid, ea trebuie sa contina un W si minim un E. In cazul in care nicio subsecventa nu se poate forma, se va afisa -1.
h2. Restricţii
* $... ≤ ... ≤ ...$
**n >= 1 si n <= 200000**
**fara cazuri particulare de cacat**
**teste generate cu random**
**sir plin de W -> -1**
**sir plin de E -> -1**
* $1 ≤ N ≤ 200000$
* Cititi cu atentie ce scrie in "Date de iesire", pentru a nu ne da un #MLC ulterior!
* Numele problemei contine exact 4 caractere "e"
* Micutul B intre timp s-a facut mare, dar tot ii place cuvantul WEEEEEE
h2. Exemplu
table(example). |_. weeee.in |_. weeee.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 7
WEEEEWE
| 1
|
h3. Explicaţie
...
Vom interschimba penultimul si ultimul cub. Acum, subsecventa care incepe de pe pozitia 1 si are lungime 6 va incepe cu litera W si va contine toti E-ii sirului initial. Asta va duce la fericirea micutului B.
== include(page="template/taskfooter" task_id="weeee") ==
