== include(page="template/taskheader" task_id="sageti") ==
Tractorel si-a cumparat un arc cu foarte multe sageti. Acesta are N sageti asezate pe un teren in linie orientate spre stanga ('<') sau in dreapta ('>').
Din motive obscure acesta si-a pus urmatoarea intrebare existentiala: 'Care ar fi numarul minim de sageti pe care le-as putea lua de pe teren astfel incat la final sa imi ramana un numar egal de sageti orientate spre dreapta cu cele orientate spre stanga.
Tractorel și-a cumpărat un arc cu foarte multe săgeți. Acesta are $N$ săgeți așezate în șir, orientate spre stânga $('<')$ sau în dreapta $('>')$. Personajul principal are dreptul la operația $ERASE$ care elimină o săgeată din șir. Cum talentul lui Tractorel este numărarea dolarilor, acesta numără săgețile la stânga din șir și le notează cu [$NRS$], respectiv $NRD$ cele poziționate la dreapta .
Dându-se un șir de $N$ săgeți acesta vrea să afle numărul minim de operații $ERASE$ astfel încât după efectuarea lor șirul să înceapă doar cu săgeți spre dreapta iar în continuarea lor să se afle doar săgeți orientate spre stânga și $NRS = NRD$.
După cum v-ați obișnuit, Tractorel vă roagă să răspundeți la $T$ întrebări.
h2. Date de intrare
Fișierul de intrare $sageti.in$ ...
Fișierul de intrare $sageti.in$ conține pe prima linie un număr natural [$T$], reprezentând numărul de teste. Fiecare din cele $T$ linii va conține un număr natural $N$ semnificând numărul de săgeți și un șir de caractere $S$ de lungime [$N$]. $N$ si $S$ sunt separate printr-un spațiu.
h2. Date de ieșire
În fișierul de ieșire $sageti.out$ ...
În fișierul de ieșire $sageti.out$ se vor afla $T$ linii, fiecare conținând câte un singur număr reprezentând răspunsul cerinței.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 15$
* $1 ≤ N ≤ 10[^6^]$
h2. Exemplu
table(example).
|_. sageti.in |_. sageti.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|2
3 >><
10 >>><<><<>>
| 1
4
|
h3. Explicație
...
Pentru simplitate vom consideră că începem numerotoarea pozițiilor de la [$1$].
În primul caz se poate aplica operația $ERASE$ pe săgeată de pe prima poziție din șir.
În al [$2$]-lea caz se poate aplica $ERASE$ pe săgețile de pe pozițiile 5, 7, 9, 10.
== include(page="template/taskfooter" task_id="sageti") ==
