5. Korálkový náhrdelník

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahni (liahen.ksp.sk). Keď budeš riešiť sadu conditions_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Paulinke na [email protected]

Kde bolo tam bolo, žili si Etka a Jemo. A žili by si šťastne až kým by nepomreli, ak by nenastal ten obávaný deň. Výročie. A Jemo naň, ako inak, zabudol. Spomenul si naň až v poslednú možnú chvíľu a rýchlo trielil do obchodu, kde úspešne kúpil pestrofarebný korálkový náhrdelník a hrdý na svoj počin zazvonil Etke pri dverách.

Lenže, beda prebeda! Jemo vrámci tohto stresujúceho nákupu zabudal na jednu mimoriadne podstatnú vec. Etka nie je veľký fanúšik príliš farebných vecí. Konkrétne, vyžaduje aby všetky jej veci mali nanajvýš dve farby.

Jemo teraz stojí pred dverami, Etka sa blíži a on potrebuje svoju chybu rýchlo napraviť. Najjednoduchšie bude vybrať časť náhrdelníka, ktorá má najviac dve farby, zvyšok odstrihnúť a vybraný úsek zviazať dokopy a podarovať Etke krásny dvojfarebný náhrdelník.

Úloha

Pomôžte Jemovi opraviť náhrdelník skôr ako Etka otvorí dvere.

Náhrdelník sa skladá z farebných koráliek. Na vstupe dostane popis farieb jednotlivých koráliek tak, ako sú za sebou poukladané v náhrdelníku. Dajte si pozor, že po poslednej korálke nasleduje hneď korálka prvá.

Vašou úlohou je nájsť najdlhší¹ súvislý úsek náhrdelníka, ktorý obsahuje najviac korálky dvoch farieb.

Formát vstupu

V prvom riadku je číslo \(1 \leq n \leq 100\,000\) udávajúce počet koráliek na náhrdelníku.

V druhom riadku je \(n\) medzerami oddelených čísel \(c_1\) až \(c_n\) (\(1 \leq c_i \leq 10^9\)) – farby koráliek v náhrdelníku.

Formát výstupu

Na prvý riadok výstupu vypíšte dĺžku najdlhšieho náhrdelníku ktorý vie Jemo vytvoriť.

Na druhý riadok vypíšte indexy prvej a poslednej korálky ktoré budú tvoriť nový náhrdelník. Dajte si pozor, že náhrdelník je kruhový.

V prípade, že je riešení viac, vypíšte ľubovoľné z nich.

Hodnotenie

Vaše riešenie bude otestované na \(5\) sadách vstupov. Za vyriešenie každej sady získate 3 body. Tieto sady sa líšia veľkosťou vstupných údajov.

Príklady

Input:

7
3 1 2 1 2 2 3

Output:

5
2 6

V tomto prípade je najlepší náhrdelník 1-2-1-2-2. Tento vstup by sa mohol nachádzať aj v sadách 2 a 4.

Input:

6
1 2 5 3 1 2

Output:

4
5 2

Všimnite si, že vo výstupe je číslo prvej korálky väčšie ako číslo poslednej. To je v poriadku, pretože náhrdelník je cyklický (posledná korálka je spojená s prvou). Chceme vybrať korálky 1-2-1-2.

Input:

5
3 9 9 3 9

Output:

5
4 3

V tomto prípade je aj pôvodný náhrdelník vyhovujúci. Správne odpovede by boli aj 1 5 alebo 5 4.

Input:

8
4 5 1 4 6 5 1 2

Output:

2
1 2

Tu sa žiaľ nedá spraviť nič lepšie ako použiť niektoré dve susedné korálky. Všimnime si, že nemôžeme vytvoriť náhrdelník 1-4-1, pretože úsek musí byť na pôvodnom náhrdelníku súvislý.