Koniec kola: 17. máj 2021 23:59
1 deň
Počet bodov:
Popis:  20b

September prišiel a farmár Jožo sa chystá na zber zeleniny zo svojho políčka. Na ňom má pekne v rade zasadených \(n\) zelenín rôznych (alebo aj rovnakých) druhov. Jožo si chce zvoliť jeden súvislý úsek poľa, z ktorého si zeleninu odloží doma; zvyškom prispeje do pohostenia pri najbližšom stretnutí dedinskej futbalovej ligy.

Okrem toho ale Jožo cez leto začal odoberať akýsi časopis o vyrovnanej strave. V ňom sa dočítal, že mu urobí dobre, ak nebude existovať jeden druh zeleniny, z ktorého by mal doma viac kusov ako z každého iného. (Tu sa ukazuje prečo sa Jožo nerozhodol proste zožrať všetko sám – mal by pocit že žije nezdravo.) Inak povedané, musia existovať aspoň dva druhy, z ktorých na jeho vybranom súvislom úseku poľa bude rovnako veľa kusov a zároveň zo žiadneho iného druhu na tom úseku nebude viac kusov.

Samozrejme, aj tak by si chcel Jožo nechať čo najviac zeleniny pre seba. Konkrétne chce, aby z každého z tých najčastejších druhov zeleniny mal doma aspoň \(k\) kusov. Povedzte mu, koľko najviac zeleniny si môže uskladniť doma, alebo aspoň že si nevie podľa svojich požiadaviek vybrať žiadny úsek poľa (a dofrasa aj s časopisom, všetky plány mu prekazil!).

Formát vstupu

Na prvom riadku sú čísla \(n\) a \(k\) – počet kusov zeleniny na poli a minimálny vyžadovaný počet kusov najčastejšieho druhu.

Na druhom riadku je \(n\) čísel \(a_1\)\(a_n\) – typy jednotlivých kusov zeleniny v poradí, v ktorom rastú na poli. Platí \(1 \le a_i \le n\).

Formát výstupu

Vypíšte jeden riadok a na ňom jedno číslo – dĺžku najdlhšieho úseku poľa, ktorý je možné vybrať, alebo \(-1\) ak nie je možné vybrať žiadny úsek.

Hodnotenie

Je 6 sád vstupov. Platia v nich nasledujúce obmedzenia:

Sada 1 2 3, 4 5 6
\(1 \leq n \leq\) \(60\) \(5\,000\) \(10\,000\) \(50\,000\) \(100\,000\)
\(1 \leq n/k \leq\) \(60\) \(5\,000\) \(20\) \(100\) \(200\)

Príklad

Input:

5 1
2 2 3 1 2

Output:

3

Pole obsahuje napr. zemiak, zemiak, mrkvu, kareláb, zemiak. Optimálne je zobrať mrkvu, kareláb a jeden zo zemiakov ktoré s nimi susedia. Futbalový guľáš získal zvyšné dva zemiaky.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.