Candale Silviu (silviu) 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ă:
- Amaric aplică doar magii de tipul 1;
- Amaric aplică doar magii de tipul 2;
- 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).