Stringhe di Fibonacci

Le stringhe di Fibonacci sono definite ricorsivamente come segue.

• Come caso base, vi sono le stringhe F(0)=b e F(1)=a.
• Per k>1, la stringa F(k) è ricorsivamente definita come la concatenazione delle due stringhe F(k-1) e F(k-2): per esempio,F(2)=F(1)F(0)=ab, F(3)=F(2)F(1)=aba, F(4)=F(3)F(2)=abaab, e così via.

Possiamo facilmente generalizzare la suddetta definizione passando dai due simboli a e b a due qualunque simboli x e y dell’alfabeto (dove x è diverso da y), ottenendo così la stringa generalizzata di Fibonacci per due parametri x e y (i due simboli).

Data una stringa S di N simboli, il tuo compito è quello di trovare il più lungo segmento di simboli consecutivi in S che sia una stringa generalizzata di Fibonacci.
Se tale segmento va dalla posizione I alla posizione J di S, estremi inclusi, allora è sufficiente riportare la coppia di numeri I e J, dove1<=I<=J<=N.

Dati in Input

Il file input.txt è composto da due righe.

• La prima riga contiene il numero N di simboli che compongono la stringa in input.
• La seconda riga contiene gli N caratteri (senza spazi di separazione) di tale stringa.

Dati in Output

Il file output.txt è composto da una coppia di interi I e J separati da uno spazio, per rappresentare il più lungo segmento di simboli consecutivi in S che sia una stringa generalizzata di Fibonacci, dove 1<=I<=J<=N: nel caso ci siano più segmenti di pari lunghezza che soddisfano le condizioni richieste, è obbligatorio riportare quello più a sinistra, ovvero quello corrispondente alle posizioni più piccole.

Assunzioni

• 1 <= N <= 10⁶

Esempi

Nota

• Nell’esempio, la risposta è motivata dal fatto che il segmento che va dalla posizione I=17 alla posizione J=21 nella stringa di input abcdbeababcdeebeedeedcacb corrisponde a F(4)=edeed ponendo x=e e y=d.