J. Интервал будах

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

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

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

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

Арёо $2418$ дахь төрсөн өдрөөрөө маш олон интервал авчээ. Тэрээр ихэд баярлан тэдгээрийг бүгдийг нь хэдэн өнгөөр будахаар шийджээ. Тэр өөртөө хэдэн дүрэм тогтоожээ. Тэрээр $a, b$, $c$ интервалууд дараах нөхцлийг нэгэн зэрэг хангахгүй бол сайхан будсан байна гэж үзнэ:

  • $a, b$, $c$ нь нэг өнгөөр будагдсан бол,
  • ,
  • ,
  • .

$i$ болон $j$ гэсэн интервал тус бүрийн хувьд: $j$-д байгаагүй дор хаяж нэг цэг $i$-д байна гэдгийг олж мэджээ.

Өгөгдсөн бүлэг интервалуудаас Арёо $k$ өнгөөр өөрт таалагдахаар будаж чадах хамгийн бага $k$ тоог олно уу.

Оролт

Эхний мөр нь $n$ ($1 ≤ n ≤ 10^{3}$) гэсэн бүхэл тоо агуулах ба энэ нь интервалийн тоог харуулна.

Дараагийн $n$ мөрүүд нь интервалын тодорхойлолтыг агуулна. Интервал тус бүр нь $s_{i}, e_{i}$ гэсэн хоёр тоогоор дүрслэгдэх ба эдгээр нь үүний ($ - 10^{5} < s_{i}, e_{i} < 10^{5}$, $s_{i} ≤ e_{i}$) эхлэл болон төгсгөлийн цэг юм. Жишээнээс тодорхой харна уу. Дөрвөлжин хаалт нь харгалзах төгсгөлийн цэгүүдийг харъяалах бол дугуй хаалт нь үл хамаарах утгыг илэрхийлнэ.

Гаралт

Интервалийг сайхан будахын тулд шаардагдах хамгийн бага өнгөний тоог илэрхийлсэн $k$ тоог гарга.

Орчуулсан: Энхгэрэл

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

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