A. Хөгжилтэйгээр Кенгерууг тоол

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

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

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

Оролт

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

Гаралт

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

Орчуулсан: zoloogg

Жишээ тэстүүд

Оролт
8
2
5
7
6
9
8
4
2
Гаралт
5
Оролт
8
9
1
6
2
6
5
8
3
Гаралт
5
Сэтгэгдлүүдийг ачааллаж байна...