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 nn events: the ii -th event had continued from the year aia_{i} to the year bib_{i} inclusive ( a_{i}<b_{i} ). Polycarpus easily learned the dates when each of nn 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 jj includes an event ii 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 nn ( 1<=n<=1051<=n<=10^{5} ) which represents the number of events. Next nn lines contain descriptions of the historical events, one event per line. The i+1i+1 line contains two integers aia_{i} and bib_{i} ( 1<=a_{i}<b_{i}<=10^{9} ) — the beginning and the end of the ii -th event. No two events start or finish in the same year, that is, aiaj,aibj,biaj,bibja_{i}≠a_{j},a_{i}≠b_{j},b_{i}≠a_{j},b_{i}≠b_{j} for all ii , jj (where iji≠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.

首页