== include(page="template/taskheader" task_id="subsir1000") ==

Poveste şi cerinţă...

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.

h2. Date de intrare

Fişierul de intrare $subsir1000.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $subsir1000.out$ ...

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

h2. Restricţii

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 100 000$
* Considerând că şirul dat este $A = (a{~1~},a{~2~},...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.

h2. Exemplu
table(example). |_. subsir1000.in |_. subsir1000.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 7
5 3 4 6 2 5 6
| 4

|
h3. Explicaţie

...

O soluţie posibila este: $3 6 2 6$

== include(page="template/taskfooter" task_id="subsir1000") ==

5449