sir

Se consideră un şir $c_1 \ c_2 ... c_n$ format din $n$ caractere din mulţimea $\{ A, B \}$.
Concatenăm şirul cu el însuşi şi obţinem un şir de lungime $2n$.
Pentru un indice $k \ (1 \leq k \leq 2n)$ considerăm subsecvenţele de lungime cel mult $n$, care se termină pe poziţia $k$, iar dintre acestea fie $s(k)$ subsecvenţa cea mai mică în ordine lexicografică.

Cerinţă

Determinaţi indicele $k$ pentru care $s(k)$ are lungimea cea mai mare.

Date de intrare

Pe prima linie a fişierului de intrare sir.in se găseşte numărul natural $n$, reprezentând lungimea şirului. Pe următoarele $n$ linii se află în ordine caracterele şirului (câte un caracter pe o linie).

Date de ieşire

Prima linie a fişierului de ieşire sir.out va conţine numărul natural $k$. În caz că există mai multe valori pentru $k$ se va alege cea mai mică.

Restricții și precizări

• $1 \leq n \leq 30 \ 000$

Exemplul 1

sir.in

8
A
B
B
A
B
A
A
B

sir.out

13