Rezolvare PBinfo #4474

Vrăjitorul Amaric a găsit un șir cu N numere, pe care vrea să-l transforme astfel încât să conțină o secvență de valori egale de lungime cât mai mare. Pentru aceasta, Amaric a pregătit două feluri de magii:

- magia de tip 1: alege două numere din șir și le schimbă între ele în șir. Această magie se poate aplica de oricâte ori.
- magia de tip 2: alege un număr din șir și îl mărește cu o valoare care este divizor al acestuia. Această magie se poate aplica cel mult o dată pentru fiecare număr din șir.

De exemplu, dacă șirul contine numerele (6, 8, 4, 8), aplicând magia de tip 1 pentru numerele 4 și 8, șirul devine (6, 8, 8, 4). Dacă aplicăm magia de tip 2 pentru numărul 4, el poate deveni 5 sau 6 sau 8.

Cerința

Scrieți un program care să determine lungimea maximă a unei secvențe de numere egale dacă:

1. Amaric aplică doar magii de tipul 1;
2. Amaric aplică doar magii de tipul 2;
3. Amaric aplică magii de tipul 1 și de tipul 2.

Date de intrare

Fișierul de intrare magie.in conține pe prima linie numărul C, care poate fi 1, 2 sau 3, reprezentând cerință care trebuie rezolvată. Pe a doua linie se află numărul N, iar pe a treia linie N numere naturale, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire magie.out va conține un număr natural reprezentând lungimea maximă a unei secvențe de numere egale, aplicând magiile permise.

Restricții și precizări

• 1 ≤ N ≤ 5.000;
• 1 ≤ numerele din șirul dat ≤ 5.000;
• pentru teste în valoare de 30 de puncte, C = 1
• pentru teste în valoare de 30 de puncte, C = 2

Exemplul 1

magie.in

1
4
6 8 4 8

magie.out

2

Explicație

Aplicând magia de tipul 1 pentru numerele 8 și 4 șirul devine (6 4 8 8).

Exemplul 2

magie.in

2
4
6 9 8 4

magie.out

3

Explicație

Aplicând magia de tip 2 pentru numărul 6 îl mărim cu 3 și devine 9.
Aplicând magia de tip 2 pentru numărul 8 îl mărim cu 1 și devine 9.
Șirul devine (9 9 9 4).

Exemplul 3

magie.in

3
4
6 9 4 8

magie.out

3

Explicație

Aplicăm o magie de tip 1 pentru numerele 6 și 9 și șirul devine (9, 6, 4, 8).
Aplicând magia de tip 2 pentru numărul 6 îl mărim cu 2 și devine 8.
Aplicând magia de tip 2 pentru numărul 4 îl mărim cu 4 și devine 8.
Șirul devine (9 8 8 8).