Doprogramovanie do: 31. január 2022 23:59
11 dní
Popisy už neodovzdávajte. Ešte stále však môžete odosielať vaše programy, za ktoré dostanete časť bodov.
Počet bodov:
Popis:  12b
Program:  8b

Záhradník Adam mal veľmi úspešný rok. Zeleniny v jeho záhrade mu narástli do neuveriteľných rozmerov. Toto je síce pekné pri tekviciach, ktoré sa vďaka sezónnemu sviatku predajú veľmi rýchlo, ale pri istom type zeleniny to je problém. Napríklad taká repa, keď je veľká, ťažko sa zo zeme vyťahuje a Adam si na pomoc musel zavolať dedka, babku, sestru, mačku a myš. Takto sa im podarilo repu vytiahnuť, no majú ešte jeden väčší problém: masívny kaleráb, v zemi zakorenený tak pevne, že potrebujú ešte viac ľudí ako na repu. Na pomoc si teda zavolali susedov, kamarátov, známych a aj ich domáce zvieratá a za odmenu im sľúbili domáce sladkosti.

Susedia tak prišli do Adamovej záhrady v nejakom poradí. Toto poradie musí ostať rovnaké počas celého procesu organizácie a ťahania kalerábu. Samozrejme, pri kalerábe musí byť čo najsilnejší človek. Zlaté pravidlo ťahania kalerábov je, že za každým človekom so silou \(F\), musí byť človek, ktorý má silu presne \(F-1\). Zoberme si príklad, kde človek A, ktorý má silu 5 je pred človekom B. Človek B teda musí mať silu 4. Ak by bol človek B silnejší, človeka A potiahne moc silno a celý rad spadne. Ak by bol slabší, kaleráb sa im vytiahnuť nepodarí. Adam je skúsený záhradník, a vie mať akúkoľvek silu a vie sa postaviť kamkoľvek do radu. Adam má teda rad ľudí, z ktorých musí niektorých vypustiť, aby sa splnilo zlaté pravidlo ťahania kalerábov. Adam sa vie taktiež postaviť hocikde s hocijakou silou. Bude mať však ale dosť starostí s ťahaním a už potrebuje pomôcť s organizáciou. Pomôžete mu postaviť čo najdlhši rad, ktorý tieto pravidlá spĺňa?

Úloha

V záhrade je \(N\) ľudí, každý so silou \(F_i\) kde \(i\) je poradie, v ktorom prišiel daný človek. Vašou úlohou je vypustiť z radu niekoľko ľudí, a vsunúť do radu Adama tak, aby tento rad spĺňal zlaté pravidlo, a zároveň bol čo najdlhší. Stačí zistiť dĺžku najdlhšieho možného radu.

Formát vstupu

Na prvom riadku dostanete dve čísla: \(1 \leq N \leq 500\,000\) – počet ľudí v rade a \(1 \leq M \leq 50\,000\,000\) – najsilnejšieho človeka v rade. Na druhom riadku dostanete \(N\) čísel \(F_i\) oddelených medzerami – silu \(i\)-tého človeka v rade.

Formát výstupu

Na výstup vypíšte jedno číslo \(L\) – najväčšiu možnú dĺžku radu.

Príklad

Input:

10 12
1 3 5 7 9 2 4 8 12 10

Output:

4

Najlepšie riešenie je napríklad zobrať čísla 1, 2 a 4 z radu a postaviť Adama so silou 3 na správne miesto.

Input:

6 5
1 2 3 4 5 4

Output:

6

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.