scoici

Raluca si Ana, prietene bune din copilarie, merg la mare. Plimbandu-se toata ziua pe malul marii incep sa stranga scoici. Dupa ce strang N scoici, Ana le insira pe o sfoara si constata ca sunt colorate in C culori. Raluca doreste acum sa aleaga din siragul format cu cele N scoici, o secventa armonioasa, cat mai lunga, pentru a-si face un colier frumos.
O secventa armonioasa este formata din scoici consecutive in sirag, care sa aiba scoici de toate culorile disponibile si fiecare sa aiba aceeasi frecventa de aparitie in secventa.
Cum numarul de scoici strans poate fi destul de mare (pentru ca fetele au multa rabdare), va este cerut ajutorul.

Cerinta

Ajutati-o pe Raluca sa determine cea mai lunga secventa armonioasa din siragul format cu cele N scoici.

Date de intrare

Fisierul de intrare scoici.in contine pe prima linie doua numere naturale separate prin spatiu N si C unde N repezinta numarul de scoici, iar C reprezinta numarul de culori. Pe cea de a doua linie se afla N numere naturale cuprinse intre 1 si C separate prin spatii, reprezintand culorile celor N scoici din sirag.

Date de iesire

Fisierul de iesire scoici.out va contine o singura linie pe care se vor afisa doua numere naturale separate printr-un spatiu, poz si lg, unde poz reprezinta pozitia in sirul de scoici de unde incepe secventa armonioasa, iar lg reprezinta lungimea acesteia.

Restrictii si precizari

• 0 < N < 100 000
• 1 < C < 11
• Culorile sunt identificate prin numere naturale cuprinse intre 1 si C.
• Pozitiile in siragul de scoici sunt numerotate de la 1 la N.
• 1 <= poz <= N
• poz+lg <= N
• Daca sunt mai multe solutii optime ca lungime, determinati pe cea cu pozitia initiala mai mica.
• Pentru datele de test se garanteaza existenta unei solutii precum si faptul ca in sirul dat exista cel putin o scoica din fiecare culoare.
  

Timp maxim de executie/test: 0.15 secunde

Gheorghe Stefan
ASE, facultatea de Cibernetica
Contact: stefangh@gmail.com