Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
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