C. Шалгалтууд

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

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

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

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

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

Хуваарийн дагуу оюутан $a_{i}$ тоотой өдөр $i$-р хичээлийн шалгалтыг өгдөг. Гэхдээ Валера багш бүртэй зөвшилцсөнөөр, $i$-р хичээлийн багш түүнийг шалгалтын хуваариас өмнө $b_{i}$ ($b_{i} < a_{i}$) өдөр шалгалтаа өгөхийг зөвшөөрсөн. Тиймээс Валера $i$-р хичээлийн шалгалтыг $a_{i}$ эсвэл $b_{i}$ өдрийн аль нэгэнд өгч болно. Бүх багш нар шалгалтын жинхэнэ өдрөөр оюутнуудын дээд амжилтын номонд шалгалтынх нь амжилтыг бүртгэж, $a_{i}$ тоогоор бүртгэсэн өдрийг бичдэг.

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

Оролт

Эхний мөр Валерагийн өгөх шалгалтын тоог харуулсан эерэг бүхэл тоо $n$ ($1 ≤ n ≤ 5000$)-г агуулна.

Дараагийн $n$ мөр бүр нь хуваарьт шалгалтын өдөр болон $i$-р шалгалтыг эрт өгөх огноог харуулсан, хоосон зайгаар тусгаарлагдсан 2 эерэг бүхэл тоо $a_{i}$ ба $b_{i}$ ($1 ≤ b_{i} < a_{i} ≤ 10^{9}$)-г агуулна.

Гаралт

Хэрэв Валера шалгалтаа өгөөд, тэдгээр шалгалтын бүх амжилтууд нь түүний дээд амжилтын номонд үл буурах огнооны дарааллаар бичигдэх бол Валерагийн сүүлийн шалгалтаа өгч болох огноог харуулах боломжит хамгийн бага тоог харуулах бүхэл тоог хэвлэ.

Орчуулсан: Солонго

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

Оролт
3
5 2
3 1
4 2
Гаралт
2
Оролт
3
6 1
5 2
4 3
Гаралт
6

Тэмдэглэл

Эхний жишээнд, Валера эхний өдрөө $2$ дахь хичээлийн шалгалтыг эхлээд өгч байна (багш хуваарьт өдрийг $3$ гэж бичсэн). Дараагийн өдөр тэр $3$ дахь хичээлийн шалгалтыг өгсөн (багш хуваарьт өдрийг $4$ гэж бичсэн), дараа нь тэр $1$-р хичээлийн шалгалтыг өгсөн (багш $5$ дахь өдрийг тэмдэглэн бичсэн). Тиймээс Валера 2 дахь өдөр сүүлийн шалгалтыг өгсөн ба огноо нь үл буурах дарааллаар бичигдэнэ: $3$, $4$, $5$.

Дараагийн жишээнд Валера эхлээд $4$ дэх өдөр нь $3$ дахь хичээлийн шалгалтыг өгч байна. Тэгээд $5$ дахь өдөр нь $2$ дахь хичээлийн шалгалтыг өгч байна. Түүний дараа Валера $6$ дахь өдрөө $1$ дэхь хичээлийн шалгалтыг өгчээ.

Сэтгэгдлүүдийг ачааллаж байна...