C. Түүх

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

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

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

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

Поликарпус сургууль дээрээ хичээл хийх маш их дуртай ба гэрийн даалгавараа маш хичээнгүйлэн хийдэг. Поликарпусын өвөө нь агуу физикч байсан учраас шинжлэх ухааны хичээлүүдэд түүнд асуудал гардаггүй байв. Өөрөөр хэлбэл , Поликарпус түүхийн хичээл дээр хэзээч цагийг хялбар өнгөрүүлдэггүй байсан.

Дэлхийн түүхтэй $n$ ширхэг чухал үйл явдлууд хамаардаг гэдгийг хүн бүхэн мэднэ. $i$-дугаар үйл явдал нь $a_i$ оноос $b_i$ ($a_i < b_i$) онуудын хооронд болсон. Өвөөгийнхөө ой тогтоох чадварыг өвлөж авсан учраас түүхийн $n$ үйл явдалын оц цагуудыг маш сайн цээжилж байсан ч багш нь улам хүнд даалгаварууд өгж байв. Поликарпус үйл явдалын эхлэх , төгсөх өдрүүдийг цээжлэх ёстойгоос гадна өөр өөр өдрүүдийг цээжлэх ёстой байв.Хэрвээ $a_j < a_i$, $b_i < b_j$ байвал, $j$-дүгээр үйл явдал $i$-дугаар үйл явдалыг агуулдаг гэсэн үг. Чиний даалгавар их энгийн, өөр үйл явдалуудыг агуулдаг үйл явдлуудын тоог ол !

Оролт

Эхний мөрөнд үйл явдалуудын тоог идэрхийлэх $n$ ширхэг ($1 ≤ n ≤ 10^5$) тоо.Дараагийн n мөрүүдэд $1$ мөрөнд $1$ үйл явдал байхаар үйл явдлуудын тайлбар. $i+1$ мөрөнд $i$-дугаар үйл явдылн эхлэл болон төгсгөлийн өдрийн илэрхийлэх 2 бүхэл $a_i$ болон $b_i$ ($1 ≤ a_i < b_i ≤ 10^9$) тоо.1 жилийн ямар ч 2 үйл явдалын эхлэл болон төгсгөлийн цаг давхцахгүй. $a_i ≠ a_j, a_i ≠ b_j, b_i ≠ a_j, b_i ≠ b_j , i, j$ ($i ≠ j$ үед).

Гаралт

Асуултын Хариу

[Орчуулга хяналт хийгдээгүй. ^_^ ... Codeforces Mongolian Translation Team]

Орчуулсан: Баттулга

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

Оролт
5
1 10
2 9
3 8
4 7
5 6
Гаралт
4
Оролт
5
1 100
2 50
51 99
52 98
10 60
Гаралт
4
Оролт
1
1 1000000000
Гаралт
0

Тэмдэглэл

In the first example the fifth event is contained in the fourth. Similarly, the fourth event is contained in the third, the third -- in the second and the second -- in the first.

In the second example all events except the first one are contained in the first.

In the third example only one event, so the answer is 0.

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