Weeee

weeee

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

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

Poveste şi cerinţă...

h2. Date de intrare

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.

Fişierul de intrare $weeee.in$ ...

h2. Date de ieşire

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

În fişierul de ieşire $weeee.out$ ...

h2. Restricţii

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

| 7
  WEEEEWE
| 1

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
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") ==