Gigel are o panglică alcătuită din benzi de 1 cm lăţime, colorate în diverse culori. Panglica are N benzi colorate cu C culori, culori pe care le vom numerota de la 1 la C. Gigel vrea ca la ambele capete ale panglicii să aibă aceeaşi culoare, dar cum nu poate schimba culorile benzilor, singura posibilitate rămâne tăierea unor bucăţi de la capete.
Cerinţă
Scrieţi un program care să determine modul de tăiere a panglicii astfel încât la cele două capete să fie benzi de aceeaşi culoare, iar lungimea panglicii obţinute să fie maximă.
Date de intrare
Fişierul de intrare panglica.in conţine:
– pe prima linie numerele naturale N şi C separate printr-un spaţiu;
– pe următoarele N linii descrierea panglicii: pe fiecare linie un număr natural de la 1 la C, reprezentând în ordine culorile fâşiilor ce alcătuiesc panglica.
Date de ieşire
Fişierul de ieşire panglica.out va conţine următoarele 4 numere:
– pe prima linie numărul de fâşii rămase;
– pe linia a doua numărul culorii care se află la capete;
– pe linia a treia câte fâşii trebuie tăiate de la începutul panglicii iniţiale;
– pe linia a patra câte fâşii trebuie tăiate de la sfârşitul panglicii iniţiale.
Restricţii
2<=N<=10000
1<=C<=200
Dacă există mai multe soluţii alegeţi pe cea în care se taie cât mai puţin din partea de început a panglicii.