Pracsiu Dan (dnprx) 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ța
Cunoscând numărul N de obiective turistice din traseu și cele N coduri ale lor (c[1], c[2], …, 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], ..., c[j]), 1 ≤ i ≤ j ≤ N
Date de intrare
Fișierul de intrare 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 de ieșire 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 ≤ N ≤ 1000- Numerele de pe al doilea rând din fișierul de intrare sunt nenule și mai mici sau egale cu
1.000.000 - Pentru cerința 1 se acordă 45 de puncte
- Pentru cerința 2 se acordă 45 de puncte
- Se acordă 10 puncte pentru exemple
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.