UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3375. [Usaco2004 Mar]Paranoid Cows 发疯的奶牛

Statistics 下载数据

Description

    约翰有N(1≤N≤100000)头奶牛,它们都可以控制自己的产奶量.一头产奶不多的奶牛会被其它奶牛嘲笑, 约翰制订一张产奶时间表,第i头奶牛在Ai_Bi时间段里产奶(0≤Ai<Bi≤10^9).这头奶牛必须在Ai的时候进入奶棚在Bi的时候离开.奶棚的门很小,同一时刻只能有一头奶牛通过. 如果第i头奶牛产奶的时间段包含第j头奶牛产奶的时间段,即A<Aj<Bj<Bi.那么,我们称这两个时间段是“巢段”.  “巢段”是一件很糟糕的事,因为第j头奶牛在奶棚的时间里第i头奶牛一直都在.这样第i头奶牛就能估计第j头奶牛的产奶量.由于产奶量被别的奶牛知道了的奶牛会发疯,所以约翰不希望“巢段”的发生.
    帮助约翰确定最大的k(1≤K≤N),在1到K的奶牛中不存在“巢段”.

Input

    第1行:奶牛的数量N.
    第2到N+1行:每行有两个用空格隔开的数字,表示这头奶牛的产奶时间段.

Output

 
    一个整数K

Sample Input

5
7 20
1 4
3 12
6 10
0 3

Sample Output

3

样例说明
第4头奶牛( 6-10)被包含于第3头奶牛(3-12).另外,1至3头奶牛不存在“巢段”

Hint

Source

Orange