#1630. Cow Crossings

Cow Crossings

FJFJNN头奶牛,奶牛们在牧场中活动。牧场是一个二维的平面,奶牛们只从y=0y=0的水平线上,以直线走到y=1y=1的点上。一开始,奶牛们都在(Ai,0)(A_i,0)上,再以直线的方式走到(Bi,1)(B_i,1)上,由于奶牛们的个性不一样,走的过程中,有些奶牛走的线路可能会相交,这样会不安全。求其中安全路线的条数。

输入格式

11行,一个整数NN

22N+1N+1行,每行两个整数AiA_iBiB_i

输出格式

输出共一行一个整数RetRet,即安全路线的条数。

样例

样例输入

4
-3 4
7 8
10 16
3 9

样例输出

2

样例解释

第1条和第3条是安全路线。

数据范围与提示

对于4040\\%的数据,1N50001\le N\le 5000.

对于100100\\%的数据,1N105,0Ai,Bi1061\le N\le 10^5,0\le |A_i|,|B_i|\le 10^6,所有AiA_i互不相等,所有BiB_i互不相等。

  • 时间限制:1000ms1000\mathrm{ms}
  • 空间限制:131072KB131072\mathrm{KB}