#5282. USACO 2014 December Contest, Bronze Cow Jog

USACO 2014 December Contest, Bronze Cow Jog

题目描述

奶牛们又出来锻炼蹄子了!有NN头奶牛在一条无限长的单车道跑道上慢跑(1 <= NN <= 100,000)。每头奶牛从跑道上的不同位置出发,有些奶牛的慢跑速度不同。

由于跑道只有一条车道,奶牛们不能相互超越。当一头速度较快的奶牛追上另一头奶牛时,她必须减速以避免撞到另一头奶牛,从而加入同一个跑步群体。

最终,不会再有奶牛相互碰撞。农夫约翰想知道当这种情况发生时,还会剩下多少个群体。请帮助他计算这个数量。

输入格式

  • 第1行:输入包含整数NN
  • 接下来NN行:每行包含一头奶牛的初始位置和速度。位置是一个非负整数,速度是一个正整数;两个数都最多为10亿。所有奶牛都从不同的位置出发,并且在输入中会按位置递增的顺序给出。

输出格式

  • 一行:一个整数,表示剩余的群体数量。

样例

样例输入

5
0 1
1 2
2 3
3 2
6 1

样例输出

2

数据范围

1 <= NN <= 100,000,位置为非负整数,速度为正整数,且均不超过10亿