Se consideră un şir c1c2...cn 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ă.
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 sir6.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 sir6.out va conţine numărul natural k. În caz că există mai multe valori pentru k se va alege cea mai mică.