시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB32266.667%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

9
8 10 3 1 6 14 4 13 7

예제 출력 1

0 1 1 2 2 2 3 3 3

예제 입력 2

4
-1 0 1 1

예제 출력 2

0 1 2 3