Fișierul intrare/ieșire	cuburi2.in, cuburi2.out	Sursă	ad-hoc
Autor	Cristian Frâncu | Dan Grigoriu	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.8 sec	Limită de memorie	15360 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Cuburi2

Notă: aceasta este problema cub1 cu limite mărite.

Un informatician care încă se mai joacă cu cuburile are un set de N cuburi de diverse culori. El le așază în linie. Privindu-le, se întreabă ce cub ar putea să elimine din șir astfel încât șirul rămas să conțină cât mai multe cuburi alăturate de aceeași culoare. Dacă există mai multe soluții, el dorește să le afle pe toate. Cuburile sunt numerotate de la 1 la N.

Date de intrare

Fișierul de intrare cuburi2.in conține pe prima linie numărul N, iar pe a doua ordine culorile cuburilor, codificate prin numere naturale între 1 și 10 inclusiv, separate prin spații.

Date de ieșire

În fișierul de ieșire cuburi2.out se va scrie, pe prima linie, lungimea secvenței maxime de cuburi alăturate de aceeași culoare care se poate obține prin eliminarea unui cub. Pe a doua linie se vor tipări, în ordine crescătoare, numerele de ordine ale cuburilor prin a căror eliminare se obține lungimea maximă.

Restricții

• 1 ≤ N ≤ 1.000.000

Exemplu

Explicație

Prin eliminarea cubului 4 se obține șirul 10 2 2 2 2 8 6 1 6 6 6, care conține 4 valori de 2 consecutive.

Prin eliminarea cubului 9 se obține șirul 10 2 2 3 2 2 8 6 6 6 6, care conține 4 valori de 6 consecutive.