1. Základné zručnosti

MisQo sedí v školskej lavici a rozvíja svoju jemnú motoriku búchaním jednej fixky o druhú. To ho po čase omrzí a rozhodne sa zabaviť sa niečím iným. Na lavici má položenú kopu ceruziek. Každá je zastrúhaná do rôznej dĺžky. Vezme lepidlo a ceruzky začne lepiť o seba a vyrábať z nich rebrík.

“Koľko najviac stupienkov vlastne môže mať ten rebrík?”, hovorí si.

Nechce sa mu ale nad tým rozmýšľať, skúste to teda zistiť zaňho.

Úloha

Na výrobu rebríka s \(k\) stupienkami potrebuje MisQo \(k+2\) ceruziek, ktoré použije takto:

• Dve ceruzky s dĺžkou aspoň \(k+1\) použije ako boky rebríka, na ktoré bude lepiť stupienky.
• Na stupienky potrebuje ďalších \(k\) ceruziek s dĺžkou aspoň \(1\), pričom širšie ceruzky budú z rebríka vytŕčať.
• Medzi jednotlivými stupienkami budú rozostupy dĺžky 1, pričom aj prvý a posledný stupienok musia mať od koncov bočných ceruziek vzdialenosť aspoň 1.

Najlepšie to celé pochopíte na obrázku:

Na prvý rebrík použil MisQo dve ceruzky dĺžky 3 ako boky a dve ceruzky dĺžky 1 ako stupienky. Aj druhý rebrík je vyrobený správne – boky sú znova z dvoch ceruziek dĺžky 3, stupienok je jedna ceruzka dĺžky 2. Na poslednom rebríku vidíme, že ceruzky môžu mať navzájom rôzne dĺžky – v tomto prípade 3 a 10¹ na boky a 2 a 3 na stupienky.

Vašou úlohou je zistiť najväčší počet stupienkov rebríka, ktorý vie Miško vyrobiť takýmto spôsobom.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 10^5\)) udávajúce počet ceruziek. Ďalej nasleduje \(n\) riadkov – každý z nich obsahuje jedno celé číslo \(a_i\), ktoré zodpovedá dĺžke \(i\)-tej ceruzky, pričom platí \(1 \leq a_i \leq 10^6\).

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo \(k\) - najväčší počet stupienkov rebríka, ktorý vie Miško vyrobiť. Ak sa nedá z ceruziek postaviť žiadny rebrík, vypíš nulu.

Príklad

Input:

5
6 
1
4
8
2

Output:

3

Ako základ rebríka použijeme dve najdlhšie ceruzky s dĺžkou 8 a 6. Zostanú nám 3 ceruzky, ktoré na tie zvislé vieme prilepiť. Rebrík teda bude mať 3 stupienky.

Input:

4
2
1
2
1

Output:

1

Ak si vyberieme ceruzky dĺžky 2 ako základ rebríka, ostanú nám dve ceruzky dĺžky 1 na stupienky. Z nich ale vieme použiť iba jednu, keďže boky rebríka sú príliš krátke.