16083번 - Хоёртын хайлтын мод 다국어

Бат бол Компьютерын Ухаанд их сонирхолтой оюутан бөгөөд олон зүйлийг гүнзгий судлах дуртай. Тэр энэ улирал өгөгдлийн бүтэц хичээл үзэж байгаа бөгөөд хоёртын хайлтын мод ямар гайхамшигтай болохыг ойлгожээ.

Хоёртын хайлтын мод гэдэг нь орой бүр нь хамгийн ихдээ хоёр хүүтэй модыг хэлэх ба баруун хүүд хадгалагдсан утга нь эцэгт хадгалагдсан утгаас их буюу тэнцүү, зүүн хүүд хадгалагдсан утга нь эцэгт хадгалагдсан утгаас эрс бага байх гэсэн бүтцийг хадгалдаг.

Illustration 1: Хоёртын хайлтын мод

Бат a₁, a₂, ..., a_n тоон дараалал орж ирэхэд эдгээр тоо нь хоёртын модны ямар ямар төвшинд хадгалагдахыг мэдэхийг хүсжээ. Төвшин гэдэг нь тухайн оройгоос модны хамгийн дээд талын орой (үндэс) хүрэхэд дамжих оройн тоог заана.

Батад тусална уу?
 

Эхний мөрөнд n (1 ≤ n ≤ 10⁴) тоо байна. Дараагийн мөрөнд n ширхэг a_i (|a_i| < 10⁶) бүхэл тоонууд байрлана.

Гаралт n ширхэг тоог агуулах бөгөөд i-р тоо ai утга ямар төвшинд хадгалагдахыг заана.