4. Prefixove rezne

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ý.

Úloha

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.

Formát vstupu

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.

Formát výstupu

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”.

Hodnotenie

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í:

Príklady

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ť.