Irinuca a descoperit un nou joc pe calculator. Pe ecran sunt plasate pe o linie n bile colorate. Culorile bilelor sunt codificate cu numere naturale. Un subşir de bile alăturate având toate aceeaşi culoare se numeşte secvenţă. O secvenţă va conţine numărul maxim de bile alăturate având aceeaşi culoare. Lungimea unei secvenţe este egală cu numărul de bile din care este compusă.
Irinuca are la dispoziţie un arc special. Trăgând cu arcul asupra unei bile, dacă aceasta face parte dintr-o secvenţă de lungime cel puţin egală cu 3, întreaga secvenţă va fi eliminată, iar bilele din dreapta secvenţei se vor deplasa spre stânga pentru a umple “golul” lăsat de bilele eliminate. Dacă imediat în stânga şi în dreapta secvenţei eliminate se găseau două secvenţe având aceeaşi culoare şi dacă secvenţa obţinută din unirea acestora după eliminare are o lungime cel puţin egală cu 3, atunci va fi şi ea eliminată la rândul ei. Procesul continuă până când secvenţele din stânga şi dreapta unei secvenţe tocmai eliminate au culori diferite sau până când lungimea secvenţei obţinute prin alăturare este mai mică decât 3 sau până când în stânga ori în dreapta unei secvenţe eliminate nu se mai găsesc bile sau până sunt eliminate toate bilele de pe ecran.
Scopul jocului este de a elimina cât mai multe bile de pe ecran. Cum Irinuca încă nu se pricepe prea bine la acest joc şi-a stabilit o strategie. Va trage cu arcul întotdeauna asupra unei bile ce face parte din secvenţa de lungime maximă de pe ecran. Dacă sunt mai multe astfel de secvenţe, ea va alege cea mai din stânga secvenţă de lungime maximă. Dacă toate secvenţele de pe ecran au lungimi mai mici decât 3, Irinuca nu va mai putea elimina nici una din ele şi jocul se încheie.

De exemplu, dacă şirul iniţial de bile este
5 1 3 3 2 2 2 2 3 1 1 5 6 4 4 4 4 7
Irinuca va acţiona asupra unei bile de culoare 2. Prin eliminare se obţine şirul de bile
5 1 3 3 3 1 1 5 6 4 4 4 4 7
din care se elimină şi secvenţa de bile de culoare 3 obţinându-se şirul de bile
5 1 1 1 5 6 4 4 4 4 7
din care se elimină şi secvenţa de culoare 1.
5 5 6 4 4 4 4 7
Cum secvenţa de bile de culoare 5 nu este suficient de lungă, aceasta nu se mai elimină. Acum Irinuca trage asupra unei bile de culoare 4 şi obţine
5 5 6 7
dar cum în stânga şi în dreapta secvenţei eliminate sunt secvenţe de culori diferite, nu se va mai elimina nici o secvenţă. Jocul se încheie deoarece nu mai există nici o secvenţă de lungime cel puţin 3 asupra căreia să se poată trage.

Cerinţă

Cunoscând numărul de bile şi culorile fiecărei bile de pe ecran se cere să se determine:
1. numărul de secvenţe de bile care se aflau iniţial pe ecran;
2. numărul de bile care rămân neeliminate de pe ecran şi culorile bilelor rămase în ordine pe ecran la finalul jocului.

Date de intrare

Fişierul de intrare arc.in conţine pe prima linie un număr natural V. Pentru toate testele de intrare, numărul V poate avea doar valoarea 1 sau 2.
A doua linie conţine un număr natural n reprezentând numărul de bile, iar a treia linie conţine n numere naturale c₁, c₂, ..., c_n separate prin câte un spaţiu, reprezentând culorile celor n bile de pe ecran.

Date de ieşire

Dacă valoarea lui V este 1, se va rezolva numai punctul 1 din cerinţă.
În acest caz, în fişierul de ieşire arc.out se va scrie un singur număr natural n1, reprezentând numărul de secvenţe de bile aflate iniţial pe ecran.
Dacă valoarea lui V este 2, se va rezolva numai punctul 2 din cerinţă.
În acest caz, în fişierul de ieşire arc.out se va scrie pe prima linie un singur număr natural n2, reprezentând numărul de bile care rămân neeliminate de pe ecran la finalul jocului, iar pe următoarele n2 linii se va scrie câte un număr natural reprezentând în ordine culorile bilelor rămase neeliminate la finalul jocului.
Dacă la finalul jocului nu mai rămâne nici o bilă neeliminată, fişierul de ieşire va conţine pe prima sa linie valoarea 0.

Restricţii

• 1 ≤ n ≤ 10 000
• 1 ≤ c₁, c₂, …, c_n ≤ 100 000
• Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerinţa a doua se acordă 80 de puncte.

Exemple

arc.in	arc.out	Explicaţii
1 18 5 1 3 3 2 2 2 2 3 1 1 5 6 4 4 4 4 7	10	V = 1 Atenţie! Pentru acest test se rezolvă doar cerinţa 1. Secvenţele sunt (5), (1), (3, 3), (2,2,2,2), (3), (1,1), (5), (6), (4,4,4,4), (7)
2 18 5 1 3 3 2 2 2 2 3 1 1 5 6 4 4 4 4 7	4 5 5 6 7	V = 2 Atenţie! Pentru acest test se rezolvă doar cerinţa 2.
2 15 1 2 2 2 2 1 1 3 3 3 4 4 4 4 3	0	V = 2 Atenţie! Pentru acest test se rezolvă doar cerinţa 2.

autor: Prof. Carmen Popescu

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com