Sir9

sir9

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

Se consideră un şir c ~1~ c ~2~ ...c ~n~ format din $n$ caractere din mulţimea {A, B}.

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≤k≤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ă.
 
Determinaţi indicele k pentru care s (k) are lungimea cea mai mare.
 

Pentru un indice $k$ ($1≤k≤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ă.

h2. Date de intrare

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

Pe prima linie a fişierului de intrare sir9.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).
h2. Date de ieşire

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

Pe prima linie a fişierului de intrare sir9.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).

h2. Restricţii