Fișierul intrare/ieșire | sageti.in, sageti.out | Sursă | ad-hoc |
---|---|---|---|
Autor | din folclor | Adăugată de | Dragos Alin Rotaru • mathboy |
Timp de execuție pe test | 0.4 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Săgeți
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.
Date de intrare
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.
Date de ieșire
Î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.
Restricții
- 1 ≤ T ≤ 15
- 1 ≤ N ≤ 106
Exemplu
sageti.in | sageti.out |
---|---|
2 3 >>< 10 >>><<><<>> |
1 4 |
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.