Fişierul intrare/ieşire:	subsir1000.in, subsir1000.out	Sursă	Algoritmiada 2011, Runda 3
Autor	Adrian Airinei	Adăugată de	Andrei Parvu •andrei.12
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Subsir1000

Pentru a cumpăra bilete la Finala Cupei, N oameni s-au aşezat la coadă. Fiecare om are locul său preferat pe care doreşte să stea, reprezentat printr-un număr strict pozitiv mai mare decât 1 şi mai mic sau egal decât N. Totuşi, toată lumea ştie că nu vor fi bilete suficiente pentru toţi, aşa că organizatorii s-au hotărât să ia un subşir de oameni de lungime maximă cărora să le dea biletele rămase. Totuşi, pentru a nu stârni suspiciuni, s-a hotarât ca în acest subşir oricare două persoane consecutive trebuie să nu aibă numerele locurilor preferate prime între ele (în acest mod organizatorii cred că persoanele nu vor ieşi în evidenţă).
Aşadar, în schimbul unei părţi din profit în valoare de 100 de puncte, organizatorii vă cer ajutorul: trebuie să determinaţi cel mai lung subşir astfel încât oricare două elemente consecutive să nu fie prime între ele.

Date de intrare

Fişierul de intrare subsir1000.in se află pe prima linie N, numărul de persoane. Pe următoarea linie se afla N numere aflate în intervalul [2, N] reprezentând locurile preferate ale persoanelor.

Date de ieşire

În fişierul de ieşire subsir1000.out trebuie să afişaţi lungimea celui mai lung subşir care respectă restricţiile date.

Restricţii

• 2 ≤ N ≤ 100 000
• Considerând că şirul dat este A = (a₁,a₂,...a_N), se numeşte subşir al lui A un şir B = (a_i1,a_i2,...a_iK) cu proprietatea că 1 ≤ i1 < i2 < ... < iK ≤ N.
• Pe organizatori nu îi interesează dacă din subşir fac parte două sau mai multe persoane cu acelaşi loc preferat. Ei le dau biletele şi îi lasă pe ei să îşi rezolve problema.

Exemplu

Explicaţie

O soluţie posibila este: 3 6 2 6

Cum se trimit solutii?