$n$ ширхэг уутат кенгеруу байна. Бүх кенгеруу бүхэл тоон хэмжээтэй. Нэг кенгерууны хэмжээ өөр нэг кенгерууны хэмжээнээс ядаж 2 дахин бага байвал уг кенгеруу нөгөөгийнхөө дотор орж чадна.

Нэг кенгеруу ихдээ 1 л кенгерууг уутандаа хийж чадна. Бас уутандаа кенгеруутай бол өөр кенгерууны уутанд орж чадахгүй. Хамгийн цөөхөн кенгеруу тоологдож байхаар бие биенийхээ уутанд орох төлөвлөгөөг зохиож өгнө үү.

Оролт

Эхний мөрөнд $n$ ($1≤ n ≤ 5·10^5$) тоо өгөгдөнө. Дараагийн $n$ мөр бүрт $i$-р кенгерууны хэмжээ $s_i$ ($1 ≤ s_i ≤ 10^5$)

Гаралт

Боломжит хамгийн цөөн харагдах кенгерууны тоо.