Moroii

Legendele spun că în adâncul cimitirului "Umbrele Pierdute", moroii își fac simțită prezența, rătăcind printre morminte și așteptând să prindă vreun nefericit aventurându-se prin cimitirul abandonat după apusul soarelui.

Din păcate, cum acest lucru nu se întâmplă foarte des, moroii se plictisesc, așa că au decis să joace de-a rătăcirea.

Cimitirul poate fi modelat ca un plan, cu X de la vest la est și Y de la sud la nord. Un moroi este așezat în centrul cimitirului la poziția $(0, 0)$, inițial îndreptat spre Est. După aceea, el primește o serie de instrucțiuni, care pot fi:

• i: Înainte, moroiul înaintează o unitate în față.
• s: Stânga, moroiul se rotește cu 90 de grade spre stânga.
• d: Dreapta, moroiul se rotește cu 90 de grade spre dreapta.
• r: Rototol, moroiul se rototolește (se învârte) și alege o directie aleatoare din cele 4 posibile.

Un moroi a urmat un set de instrucțiuni și a ajuns la poziția $(x, y)$. Acum se întreabă care este distanța maximă la care se poate afla de poziția inițială. Ajutați-l!

Distanța de la $(0, 0)$ la $(x, y)$ este $|x| + |y|$.

Date de intrare

Pe prima linie se găsește numărul $N$, numărul de instrucțiuni.
Pe următoarea linie se află un șir de caractere de lungime $N$, care reprezintă, în ordine, operațiile efectuate de moroi.

Date de ieșire

Pe unica linie afișati numărul cerut.

Restricții și precizări

• $1 \leq N \leq 10^5$.
• Se garantează că datele din input sunt corecte.

Exemplul 1

stdin

10
isisirdisi

stdout

3

Explicație

i: Din $(0, 0)$ merge în $(1, 0)$, îndreptat spre Est.
s: Rămâne în $(1, 0)$, se îndreaptă spre Nord.
i: Din $(1, 0)$ merge în $(1, 1)$, îndreptat spre Nord.
s: Rămâne în $(1, 1)$, se îndreaptă spre Vest.
i: Din $(1, 1)$ merge în $(0, 1)$, îndreptat spre Vest.
r: Rămâne în $(0, 1)$, se îndreaptă spre Nord.
d: Rămâne în $(0, 1)$, se îndreaptă spre Est.
i: Din $(0, 1)$ merge în $(1, 1)$, îndreptat spre Est.
s: Rămâne în $(1, 1)$, se îndreaptă spre Nord.
i: Din $(1, 1)$ merge în $(1, 2)$.

Așadar, ajunge la o distanță de 3 față de origine.

Exemplul 2

stdin

59
dsisididdsiiiriirrssridrsssiiddisssiirirdiisisriidisiiisisi

stdout

18