Traseu

De-a lungul unui traseu se află mai multe obiective turistice identificate printr-un număr natural numit cod. Popularitatea unui obiectiv turistic este dată de numărul divizorilor primi din descompunerea în factori primi a codului său. Cu cât un cod are mai mulți divizori primi, cu atât obiectivul cu acel cod este mai popular. Numim secvență populară o succesiune de obiective turistice care conține un singur obiectiv cu popularitate maximă, iar acesta se află fie la începutul, fie la finalul secvenței. Lungimea unei secvențe populare este dată de numărul său de obiective.

Cerință

Cunoscând numărul $N$ de obiective turistice din traseu și cele $N$ coduri ale lor ($c_1,c_2,\dots,c_N$), să se determine:

1. Obiectivele turistice de popularitate maximă,
2. Lungimea maximă a unei secvențe populare de forma ($c_i,c_{i+1},\dots,c_j$), $1 \leq i \leq j \leq N$

Date de intrare

Fișierul traseu.in conține pe prima linie numărul $N$ de obiective și cerința $C$ (separate printr-un spațiu), iar pe al doilea rând $N$ numere naturale separate prin câte un spațiu, reprezentând codurile obiectivelor turistice.

Date de ieșire

Fișierul traseu.out va conține:

• pentru cerința 1: un șir de numere separate prin câte un spațiu reprezentând codurile celor mai populare obiective turistice, în ordinea apariției lor în fișierul de intrare;
• pentru cerința 2: o singură valoare reprezentând lungimea maximă a unei secvențe de numere succesive din șirul dat, care conține un singur obiectiv de popularitate maximă aflat la unul din capetele sale.

Restricții și precizări

• $1 \leq N \leq 1 \ 000$;
• Numerele de pe al doilea rând din fișierul de intrare sunt nenule și mai mici sau egale cu $10^6$;
• Pentru cerința $1$ se acordă $45$ de puncte;
• Pentru cerința $2$ se acordă $45$ de puncte;
• Din oficiu se acordă $10$ puncte.

Exemplul 1

traseu.in

8 1 
12 6 30 18 10 50 15 70

traseu.out

30 70

Explicație

Cerința este $1$. Dintre cele $8$ obiective turistice cele mai populare sunt cele cu codurile $30$ și $70$, fiecare având $3$ divizori primi.

Exemplul 2

traseu.in

8 2 
12 6 30 18 10 50 15 70

traseu.out

5

Explicație

Secvențele populare de lungime maximă pot fi 30 18 10 50 15 sau 18 10 50 15 70.