Unirea pentru Performanta IX-X 2024 | tralala

Cerință

Gheorghe a început cursuri de pian și a învățat că poate crea o gamă alegând $7$ note din setul de $12$ note pe care le are pianul. Acesta a primit ca temă pentru acasă de la profesorul lui Tiberiu, să compună o progresie. Pentru ca melodia să sune armonios, profesorul Tiberiu l-a invățat faptul că trebuie să folosească doar note dintr-o singură gamă. De asemenea, acesta i-a cerut ca melodia să fie cât mai lungă.

Notele sunt numerotate de la $1$ la $12$ și pentru ca tema să fie cât mai simplă, Tiberiu i-a spus să pună notele din gama aleasă sub forma unei melodii care să aibă prima notă mai mică decât a doua și să nu fie 2 note egale alăturate. De exemplu, dacă se alege gama $1$, $2$, $3$, $4$, $7$, $9$, $10$, notele din acea gamă trebuie folosite pentru a crea acea secvență.(Un exemplu de melodie formată corect ar fi: $1$, $2$, $3$, $4$, $3$, $2$, $7$, $9$, $10$, și incorect ar fi: $2$, $1$, $3$, $4$, $3$, $2$, $7$, $9$, $10$ sau $1$, $2$, $2$, $4$, $3$, $2$, $7$, $9$, $10$).
Principalul scop al lui Gheorghe e să selecteze gama de $7$ note astfel încât să creeze cea mai lungă melodie care să respecte aceste condiții și să prezinte această melodie.

Gheorghe se gândea profund la o shaorma în timpul cursului și nu a înțeles mare lucru. El a încercat să își facă tema, însă melodia suna mediocru. Ajutați-l pe Gheorghe să repare melodia selectând doar o gamă din ea și rearanjând notele gamei astfel încât Tiberiu să îl mai primească în continuare la cursuri. El trebuie să formeze cea mai lungă melodie care să respecte condițiile puse de Tiberiu.

Date de intrare

Pe prima linie a fișierului de intrare tralala.in se află numărul natural $N$ de note pe care le-a folosit inițial Gheorghe.
Pe a doua linie a fișierului de intrare tralala.in se află un șir de $N$ numere naturale de la $1$ la $12$ ce reprezintă înșiruirea de note a melodiei inițiale.

Date de ieșire

Pe prima linie a fișierului de ieșire tralala.out se va afla un număr natural $L$ reprezentând numărul de note folosite după ce melodia a fost reparată.
Pe a doua linie a fișierului de ieșire tralala.outse va afla un șir de numere naturale separate prin spații, de la $1$ la $12$ ce reprezintă melodia pe care Gheorghe i-o prezintă lui Tiberiu la următoarea oră de curs. (merge pe mâna voastră)

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$;
• Toate notele din șirul inițial și final vor fi de la $1$ la $12$
• Se garantează că în melodia inițială se vor afla cel puțin $7$ note diferite
• Punctajul pentru fiecare din cele $50$ de teste se va calcula după urmatoarea formulă: Fie $L$ lungimea obținută de soluția trimisă de voi și $L_o$ lungimea obținută de soluția comisiei. Dacă soluția este corectă și respectă regulile de mai sus, punctajul obținut pentru fiecare test este: $2 \cdot min(1, \frac{L}{L_o}^2)$

Exemplul 1

tralala.in

20
1 5 12 3 10 5 2 6 11 2 2 3 1 6 12 3 9 5 8 8

tralala.out

17
1 2 3 5 6 8 12 8 6 5 3 2 1 2 3 5 12 

Explicație

Această melodie are în componență $17$ note, obținând punctajul maxim.

Exemplul 2

tralala.in

10
1 1 1 2 2 3 4 5 6 7

tralala.out

9
1 7 3 5 4 2 7 2 1

Explicație

Această soluție este compusă din $9$ note, iar melodia optimă din $10$, deci punctajul obținut pe acest test ar fi $2 \cdot \frac{9}{10}^ 2 = 1.62$