Prišlo leto. Poznáte to, prázdniny, oddych, kľud. Žaba sa tiež tešil na túto udalosť. Prišiel domov, hodil sa na posteľ a okamžite z nej spadol.
Celý ubolený sa spamätávajúc pozerá, čo sa stalo s jeho útulnou a pohodlnou postieľkou, že ho takto odmieta. Na jeho zhrozenie zistil, že mama Žabica mu poupratovala izbu a natlačila všetko do škatulí pod Žabovu posteľ. Trochu jej to ale nevyšlo. Posteľ teraz stojí nakrivo, pretože škatule sú vyššie ako samotná posteľ!
Žaba sa teda rozhodol, že vynesie škatule na povalu. Chcel by to ale, pochopiteľne, urobiť na čo najmenej otočení. Začal ukladať škatule jednu na druhú, no všimol si, že niektoré sú trochu vlhké. Ako vieme, vlhké, poloprázdne škatule udržia menej, než také škatule plné kníh (tie vydržia hocičo). Žaba teda odhadol pevnosť každej škatule, usporiadal ich podľa svojich odhadov a konečne išiel spať. Pomôžte mu a rozdeľte škatule na čo najmenej veží, aby ich mohol odniesť, keď vstane.
Úloha
Máte pred sebou \(n\) rovnako veľkých škatúl, líšiacich sa iba ich pevnosťou, usporiadaných podľa ich pevnosti. Pevnosť škatule predstavuje počet škatúľ, ktoré môžu byť vo veži položené nad danou škatuľou (teda škatuľa s pevnosťou \(0\) musí byť na vrchu veže, škatuľa s pevnosťou \(1\) môže byť buď na vrchu alebo druhá zhora atď.). Zistite, koľko najmenej veží vie Žaba z týchto škatúľ postaviť, ak musí použiť všetky škatule!
Formát vstupu
Na začiatku vstupu sa nachádza číslo \(n\) (\(1 \leq n \leq 10^5\)) – počet škatúľ, ktoré Žaba našiel pod posteľou. Na ďalšom riadku je \(n\) medzerou oddelených čísel (zoradených vzostupne) popisujúcich pevnosti jednotlivých škatúľ – číslo na \(i\)-tom mieste určuje pevnosť \(i\)-tej škatule. Pevnosť každej škatule je celé číslo medzi \(0\) a \(10^5\) vrátane.
Formát výstupu
Na výstup vypíšte jedno číslo – najmenší počet veží, ktorý sa dá postaviť za použitia všetkých škatúľ.
Upozornenie
Na získanie plného počtu bodov za popis je potrebné vyriešiť túto úlohu v najlepšej možnej asymptotickej časovej zložitosti. Plný počet bodov za program sa dá získať aj riešeniami s trochu horšou časovou zložitosťou.
Príklad
Input:
3
0 1 2
Output:
1
Všetky škatule môžeme naukladať do jednej veže.
Input:
4
2 2 2 2
Output:
2
Ak by sme chceli postaviť iba jednu vežu, najspodnejšia škatuľa by musela mať pevnosť aspoň 3. Môžeme však postaviť dve veže po dve škatule, alebo jednu vežu z troch škatúľ a jednu vežu z jednej škatule.
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.