Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.
Stačí, že pôjdeš na stránku Programátorskej Liahni (liahen.ksp.sk). Keď budeš riešiť sadu loops_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.
Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Jarovi na [email protected]
Prefix má rád rezne. Nedávno pribudla v Bratislave nová reštaurácia a všetci kamaráti, čo ju už navštívili Prefixovi vraveli, že tam robia tie najlepšie rezne. Keďže Prefix rád skúša nové chute rezňov, rozhodol sa, že tam zájde a objedná si všetky druhy rezňov, ktoré tam pripravujú. Po príchode však zistil, že objednávanie funguje v tejto reštaurácii veľmi zvláštnym spôsobom.
V reštaurácii je dlhý pult, na ktorom sú v jednom rade poukladané rezne rôznych druhov – černohorský, kyjevský, horčicový… Pri objednávaní si kupujúci vyberie súvislý úsek rezňov na pulte a čašníci mu naservírujú všetky rezne z tohto úseku. Avšak, pri jednej návšteve je možné si vybrať iba jediný (aj keď ľubovoľný) úsek.
Prefix by si už pri prvej návšteve chcel kúpiť z každého druhu rezňa aspoň jeden (nech teda zistí, ktoré rezne sú najlepšie), nechce to však s kupovaním prehnať a chcel by kúpiť čo najmenej rezňov.
Pomôžte Prefixovi vybrať najkratší úsek rezňov na pulte, ktorý obsahuje aspoň jeden z každého druhu rezňov. Samozrejme, môže sa stať, že na pulte sa nenachádzajú všetky druhy rezňov, ktoré reštaurácia ponúka (napríklad im práve došla horčica) a vtedy bude Prefix veľmi sklamaný.
V reštaurácii ponúkajú $m$ rôznych druhov rezňov a na pulte ich je v jednom rade vyložených $n$. Vašou úlohou je nájsť dĺžku najkratšieho súvislého úseku, ktorý obsahuje všetkých $m$ druhov rezňov, poprípade prehlásiť, že taký úsek neexistuje.
Na prvom riadku vstupu dostaneme dve celé čísla $n$ a $m$ – počet rezňov na pulte a počet rezňov v ponuke. Platí $m \leq n$. Druhy rezňov si označujeme číslami od $1$ po $m$.
Na druhom riadku je $n$ čísel $x_1, x_2 … x_n$ z rozsahu 1 až $m$, číslo $x_i$ reprezentuje druh $i$-teho rezňa na pulte.
Na jediný riadok výstupu vypíšte dĺžku najkratšieho úseku obsahujúceho aspoň jeden z každého druhu rezňov. Ak takýto úsek neexistuje, vypíšte “-1”.
Vaše riešenie bude otestované na $3$ sadách vstupov. Za vyriešenie každej sady získate 5 bodov. Tieto sady sa líšia veľkosťou vstupných údajov.
V nasledujúcej tabuľke označuje $n$ počet rezňov na pulte. Vo vstupných sadách platí:
| Číslo sady | 1 | 2 | 3 |
|---|---|---|---|
| maximálne $n$ | $100$ | $2\,000$ | $1\,000\,000$ |
Input:
8 4
1 4 3 4 3 2 2 1
Output:
5
Správnou možnosťou je vybrať úsek začínajúci na pozícii 4 a končiaci na pozícii 8. Tento úsek má dĺžku 5 a naozaj obsahuje všetky čísla od 1 po 4. Rozmyslite si, že kratší úsek s danou vlastnosťou naozaj neexistuje.
Input:
4 3
1 1 2 1
Output:
-1
Na pulte nie je vystavený rezeň druhu 3, preto neexistuje žiaden úsek spĺňajúci požadovanú vlastnosť.