Aranjare

La începutul anului școlar, un profesor de informatică a primit lista notelor celor $N$ elevi din clasa a IX-a cu care va lucra în laborator. Acestea sunt numere naturale mai mari sau egale cu $3$. Pentru a învăța mai bine informatica, elevii vor fi împărțiți în grupe de studiu, astfel încât, pentru fiecare grupă, toate notele elevilor din grupă să fie divizibile cu cea mai mică notă a unui elev din acea grupă. Într-o grupă poate fi și un singur elev.

De exemplu:

• o grupă poate conține elevi cu notele $5$, $10$; deoarece $5$ este nota minimă din grupă, iar $10$ este divizibil cu $5$;
• o grupă NU poate conține elevi cu notele $3$, $7$; deoarece $3$ este nota minimă din grupă, iar $7$ nu este divizibil cu $3$.

Cerință

Scrieți un program care citește numărul de elevi și notele acestora și determină numărul minim de grupe în care pot fi împărțiți elevii conform regulii precizate.

Date de intrare

Fișierul de intrare aranjare.in conține:

• Pe prima linie un număr natural, $N$, reprezentând numărul de elevi;
• Pe a doua linie două numere naturale $\text{nota}[1]$ și $\text{nota}[2]$, reprezentând notele primilor doi elevi
• Următoarele note vor fi generate folosind formula: $\text{nota}[i] = (17 \cdot \text{nota}[i - 2] + 35 \cdot \text{nota}[i - 1]) \text{ mod } 666 \ 013 + 3$

Date de ieșire

Fișierul de ieșire aranjare.out va conține un număr natural $G$, reprezentând numărul minim de grupe ce pot fi formate.

Restricții și precizări

• $1 \leq N \leq 2 \ 000 \ 000$
• $3 \leq \text{nota}[1], \text{nota}[2] \leq 500 \ 000$
• Pentru teste în valoare de $40$ puncte, $N \leq 1 \ 000$.
• Pentru alte teste în valoare de $40$ puncte, $N \leq 100 \ 000$.

Exemplul 1

aranjare.in

6
3 7

aranjare.out

4

Explicație

Notele elevilor sunt: $3$, $7$, $299$, $10587$, $375631$, $6807$.

Acestea pot fi împărțite în $4$ grupe:

1. $[3, 10587, 6807]$
2. $[7]$
3. $[299]$
4. $[375631]$

Exemplul 2

aranjare.in

11
3 10

aranjare.out

8

Explicație

Notele elevilor sunt: $3$, $10$, $404$, $14313$, $507826$, $34883$, $529768$, $486530$, $60102$, $384388$, $489044$.

Acestea pot fi împărțite în $8$ grupe:

1. $[3, 14313, 60102]$
2. $[10, 486530]$
3. $[404]$
4. $[34883]$
5. $[384388]$
6. $[489044]$
7. $[507826]$
8. $[529768]$