G. Оочир

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

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

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

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

Өвлийн нэгэн хүйтэн орой манай баатар Вася галт тэрэгний буудал дээр Codeforces-ын аварга шалгаруулах финалын тэмцээн уруу явах билет худалдан авхаар оочирлон зогсож байв. Яг урьдын адилаар билет худалдагч 5-н минут гараад ирье гэж хэлэн 1 цаг алга болж орхив. Иймд Вася зүгээр суухын оронд уг оочирийн механизм дээр дүгнэлт хийж эхэлжээ. Харин үр дүн нь түүнийг үнэхээр гайхшруулж гэнэ.

Оочирт зогсож буй хүн болгон нь 2 тоогоор дүрслэгдэнэ. Үүнд тухайн хүний одоо хөөцөлдөж буй ажил нь хэр чухал болохыг илэрхийлэх $a_{i}$ тоо (уг тоо нь их болох тусам тухайн хүний ажил улам чухал болно гэсэн үг юм) болон тухайн хүний санаа зовон ичиж буй дүр зургийг илэрхийлэх $c_{i}$ тоонууд байна. Мөн $a_{i}$ тоонууд нь $1$-ээс $n$ хүртэлх тоонуудын сэлгэмэл үүсгэж байх юм.

Оочирийг яг одоо $n - 1$ хүнээс тогтож байна гэж үзье. Одоо $n$ дугаартай хүн уг оочирт хэрхэн орж ирэхийг харцгаая. Эхлээд тэрээр оочирийн төгсгөлд очиж зогсох бөгөөд дараах үйл явц өрнөх юм: Хэрэв түүний урд зогсож байгаа хүний хөөцөлдөж буй ажлын чухал байдал $a_{i}$ нь $a_{n}$-аас бага байвал тэд байраа сольж зогсоно (энэ нь дараах хэлбэртэй харагдана: $n$ дугаартай хүн урд зогсож буй хүнээсээ "Хмм... өршөөгөөрэй уг ажил мань надад их чухал байгаа юм... та намайг урдуураа оруулаач?"). Дараа нь тэрээр дахин урд зогсож байгаа хүнээсээ ингэж асууна гэх мэтчилэн үргэлжлэх юм. Гэхдээ $a_{i}$ нь $a_{n}$-ээс их байх тохиолдолд тэрээр дахин оочир урагшлахаа зогсооно. Түүнчлэн $n$ дугаартай хүн нь $c_{n}$-аас олон удаа уг үйлдлийг гүйцэтгэж чадахгүй юм. Өөрөөр хэлбэл тэрээр хамгийн ихдээ өөрийн санаа зоволтыг илэрхийлэх $c_{n}$ удаа л уг үйлдлийг хийнэ.

Бид уг бодлогыг бодохдоо $n$ дугаартай хүн оочирт ирэхэд $n - 1$ дугаартай хүнтэй байраа солих үйл явцууд зогсоно гэж үзэх юм. Хэрэв солилт нь боломжтой байвал энэ нь байраа эзлэх хэрэгтэй байна.

Таны даалгавар бол Васяд туслан дээр дүрслэгдсэн үйлдлүүдийг гүйцэтгэж, бүх солилтууд дууссаны дараа оочирт зогсон хүмүүсийн дарааллыг олж өгөх юм.

Оролт

Эхний мөрөнд бүхэл тоо $n$ өгөгдөх ба энэ нь оочирт зогсох хүмүүсийн тоог илэрхийлнэ ($1 ≤ n ≤ 10^{5}$). Дараагийн $n$ мөрөнд хүмүүсийн тайлбар болох зайгаар тусгаарлагдсан бүхэл тоонууд $a_{i}$ болон $c_{i}$ ($1 ≤ a_{i} ≤ n$, $0 ≤ c_{i} ≤ n$) нь тэдгээрийн ирсэн дарааллаар өгөгдөнө. Мөн хүмүүсийн тайлбар болгон нь дан мөрөнд өгөгдөх ба бүх $a_{i}$-ууд нь ялгаатай байна.

Гаралт

Дээрх дүрмүүдийг дагуу үүсэх оочирийг эхнээс нь эхлэн төгсгөл хүртэл илэрхийлэх $1$-ээс $n$ хүртэлх тоонуудын сэлгэмэлийг хэвлэнэ үү. Уг хэвлэх сэлгэмэлийн $i$-т байх тоо нь бүх солилтын дараа оочирийн $i$-р байранд зогсож байх хүний дугаарыг илэрхийлнэ. Хүмүүс нь оролтод өгөгдсөн дарааллаараа $1$-ээс эхлэн дугаарлагдсан байх юм. Мөн тоонуудыг зайгаар тусгаарлан хэвлэнэ үү.

Орчуулсан: Баатархүү

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

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