题目链接：

 

题目：

　　

F. 蚂蚁

Time limit per test: 0.5 seconds

Time limit all tests: 5.0 seconds

Memory limit: 256 megabytes

Accept / Submit: 112 / 336

水平线上有 N 只蚂蚁，每只蚂蚁的位置及大小均不同。他们沿着 X 轴爬行，有的向左，有的向右，爬行的速度是一样的，两只蚂蚁相遇大一点的会吃掉小的。

现在从左到右给出每只蚂蚁的大小和爬行的方向（0 表示向左，1 表示向右）。问足够长的时间之后，能剩下多少只蚂蚁？

Input

第 1 行：一个整数 N，表示蚂蚁的数量 (1≤N≤105)。

第 2 到 N+1 行：每行两个数 Ai,Bi (1≤Ai≤109，Bi∈{

0,1})，中间用空格分隔，分别表示蚂蚁的大小及爬

行的方向，Bi=0 表示向左，Bi=1 表示向右。

对于 3/8 的数据，存在 x 满足：所有坐标比 x 小的蚂蚁向左爬、坐标比 x 大的蚂蚁向右爬；或者所有坐标比 x 小的蚂蚁向右爬、坐标比 x 大的蚂蚁向左爬。

Output

输出最终剩下的蚂蚁的数量。

Examples

input

54 03 12 01 05 0

output

2

题解：

　　可以通过简单的栈模拟，对于向左走的蚂蚁如果没有向右走的蚂蚁直接加入进栈，如果有，则比较大小，向左的蚂蚁大吃掉向右走的蚂蚁（pop），否则是被吃掉。

　　对于向右走的直接加入栈中。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
            
           
          
         
        
       
      

 

 

你努力的时候，比你厉害的人也在努力。