E. Хонь

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

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

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

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

Мэдээллийн технологийн хөгжил нь хүний үйл ажиллагааны бүхий л салбарт нэвтэрч байна. Хамгийн сүүлийн үеийн технологийг фермерт хүртэл ашиглаж байна. Бахархмаар биш гэж үү!

Том фермийн нугад хонь бэлчээрлэдэг. Ерөнхийдөө $n$ хонь байдаг бөгөөд тэд тус бүрдээ $1$-ээс $n$ хүртэлх тодорхой нэг тоог агуулдаг. Учир нь тэд маш адилхан харагддаг учраас тэднийг хооронд нь ялгах хэрэгтэй, үүнээс гадна та тэдгээрийн тус бүрийн мэдээллийг санаж байх ёстой! Нуга нь $1$-ээс хязгааргүй дугаарлагдсан хязгааргүй тооны бүсүүдээс бүрддэг. $i$ хонь $l_{i}$-ээс $r_{i}$ бүсэд дуртай гэдгийг бид мэдэж байгаа.

Хонь хариулдаг хоёр хоньчин байдаг: Нэгдүгээр бас Хоёрдугаар. Нэгдүгээр хоньчин өглөө эрт босч хонинуудыг зүлэг рүү бэлчээдэг. Харин Хоёрдугаар хоньчин орой бүх хонийг хурааж авчирдаг.

Нэгэн өглөө Нэгдүгээр хоньчин босдог цагаасаа арай орой сэрсэн учраас түүнд хонинуудыг зүлэгрүү бэлчээх хангалттай цаг байсангүй. Тиймээс тэр хоёулаа нэг бүс нутагт дуртай хоёр хонь бүрийг хамтад нь холбожээ. Тэгээд энэ нь Хоёрдугаар хоньчинд илүү амар, ажиллагаа багатай байна гэж тэр боджээ. Учир нь хонинууд хэтэрхий хол таралгүй, хоорондоо ойр ойрхон байна.

Орой Хоёрдугаар хоньчин зүлгэн дээр ирээд хонинуудыг цуглуулж, тэднийг нэг эгнээнд жагсаах гэж оролдов. Гэвч хонинууд түүний хүссэн шиг нэг эгнээнд орсонгүй. Хоёрдугаар хоньчинд хонинуудын холбоосыг тайлах боломж, чадал байсан учраас тэр тэднийг нэг нөхцөлтэйгээр энэ хэвээр нь үлдээв: Тэр холбоотой хоёр хонины хоорондын хамгийн хол зай нь аль болох бага байхаар хонинуудыг нэг эгнээнд жагсаахыг хүссэн. Хонины хоорондын зай гэдгийг тухайн хоёр хонины дунд байгаа хонины тоо гэж ойлгоно.

Хоёрдугаар хоньчинд зөв зохицуулалт хийхэд тусална уу.

Оролт

Оролтын эхний мөрөнд $n$ ($1 ≤ n ≤ 2000$) бүхэл тоо байна. Дараагийн $n$ мөр бүр $l_{i}$, $r_{i}$ $(1 ≤ l_{i}, r_{i} ≤ 10^{9}; l_{i} ≤ r_{i})$ хоёр бүхэл тоог агуулна.

Гаралт

Зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоонуудыг агуулсан нэг мөр хэвлэнэ. Энэ нь бидний хайж буй зохион байгуулалт юм. $i$-р утга нь зөв зохион байгуулагдсан мөрийн зүүнээсээ $i$-р байрлалд байх хонины дугаар юм.

Хэд хэдэн оновчтой зохион байгуулалт байгаа бол тэдгээрийн аль нэгийг хэвлээрэй.

Орчуулсан: Даариймаа

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

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