maxdiv

Adrian este pasionat de matematică. El utilizează denumirea maxdiv pentru numărul care are cei mai mulţi divizori, dintre numerele unui şir dat. Adrian ştie că o secvenţă este un subşir de numere care apar pe poziţii consecutive într-un şir. El denumeşte secvenţă maxdiv o secvenţă din şir, formată din cel puţin două numere, ce începe şi se încheie cu un număr maxdiv şi nu conţine alte numere maxdiv în interior. Având la dispoziţie un şir de n numere naturale, doreşte să afişeze cea mai lungă secvenţă maxdiv şi numărul de secvenţe maxdiv din şir. Dacă şirul de numere dat conţine mai multe secvenţe maxdiv de aceeaşi lungime maximă, se va afişa prima secvenţă de acest tip din şir.

Cerinţă

Scrieţi un program care afişează, pentru un şir dat format din $n$ numere naturale numărul de secvenţe maxdiv şi cea mai lungă secvenţă maxdiv.

Date de intrare

Fişierul de intrare maxdiv.in conţine pe prima linie numărul $n$ separat printr-un spaţiu de un număr natural $t$, care reprezintă cerinţa: $1$, dacă se cere numărul de secvenţe maxdiv, respectiv $2$ dacă se cere cea mai lungă secvenţă maxdiv. Linia a doua din fişier conţine cele $n$ numere naturale ale şirului dat.

Date de ieşire

Fişierul de ieșire maxdiv.out va conţine pe prima linie un număr natural ce reprezintă numărul de secvenţe maxdiv, pentru şirul de numere dat, dacă cerinţa este $1$. Dacă cerinţa este $2$, fişierul de ieşire va conţine un şir de numere naturale, separate între ele prin câte un spaţiu, ce reprezintă cea mai lungă secvenţă maxdiv din şirul dat.

Restricţii şi precizări

• $2 \leq n \leq 1 \ 000$
• $2 \leq x_i \leq 1 \ 000 \ 000$, unde $x_i$ reprezintă un număr din şirul dat
• Şirul de numere conţine cel puţin o secvenţă care începe şi se încheie cu un număr maxdiv
• Pentru cerința $1$ se acordă $40\%$ din punctaj, iar pentru cerința $2$ se acordă $60\%$ din punctaj.

Exemplul 1

maxdiv.in

7 1
22 60 64 125 315 24 150

maxdiv.out

2

Explicație

Cerinţa $1$
Şirul de numere dat conţine $3$ numere maxdiv: $60$, $315$ şi $150$ (au fiecare $12$ divizori) și $2$ secvenţe maxdiv : $60$, $64$, $125$, $315$ şi $315$, $24$, $150$.

Exemplul 2

maxdiv.in

7 2
22 60 64 125 315 24 150

maxdiv.out

60 64 125 315

Explicație

Cerinţa $2$
Şirul de numere dat conţine $2$ secvenţe maxdiv: $60$, $64$, $125$, $315$ şi $315$, $24$, $150$. Cea mai lungă secvenţă este $60$, $64$, $125$, $315$.