CF137C.History
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Polycarpus likes studying at school a lot and he is always diligent about his homework. Polycarpus has never had any problems with natural sciences as his great-great-grandfather was the great physicist Seinstein. On the other hand though, Polycarpus has never had an easy time with history.
Everybody knows that the World history encompasses exactly n events: the i -th event had continued from the year ai to the year bi inclusive ( a_{i}<b_{i} ). Polycarpus easily learned the dates when each of n events started and ended (Polycarpus inherited excellent memory from his great-great-granddad). But the teacher gave him a more complicated task: Polycaprus should know when all events began and ended and he should also find out for each event whether it includes another event. Polycarpus' teacher thinks that an event j includes an event i if a_{j}<a_{i} and b_{i}<b_{j} . Your task is simpler: find the number of events that are included in some other event.
输入格式
The first input line contains integer n ( 1<=n<=105 ) which represents the number of events. Next n lines contain descriptions of the historical events, one event per line. The i+1 line contains two integers ai and bi ( 1<=a_{i}<b_{i}<=10^{9} ) — the beginning and the end of the i -th event. No two events start or finish in the same year, that is, ai=aj,ai=bj,bi=aj,bi=bj for all i , j (where i=j ). Events are given in arbitrary order.
输出格式
Print the only integer — the answer to the problem.
输入输出样例
输入#1
5 1 10 2 9 3 8 4 7 5 6
输出#1
4
输入#2
5 1 100 2 50 51 99 52 98 10 60
输出#2
4
输入#3
1 1 1000000000
输出#3
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.