#2170. Cow Jog

    ID: 2170 传统题 1000ms 256MiB 尝试: 1 已通过: 0 难度: 10 上传者: 标签>年份2014竞赛USACO其他离散化数据结构并查集树状数组

Cow Jog

题目描述

奶牛又在外面活动蹄子了!有N\red{N}头牛在无限长的单车道轨道上慢跑1\red{(1≤}N\red{N≤}100000\red{100000)}。每头奶牛都从赛道上一个不同的位置出发,有些奶牛慢跑以不同的速度。

由于跑道上只有一条车道,奶牛无法相互超越。当奶牛追上另一头奶牛的速度越快,她必须减速以避免与另一头奶牛相遇,成为同一跑步组的一员。最终,再也不会有奶牛相撞了。农民约翰不知道发生这种情况时会剩下多少人。请帮忙他计算这个数字。

输入格式

输入的第一行包含整数N\red{N}

以下N\red{N}行分别包含一头奶牛。位置为非负整数,速度为正整数这两个数字最多为10\red{10}亿。所有奶牛都从不同的位置,这些位置将以递增的顺序在输入。

输出格式

指示剩余组数的单个整数。

样例

输入样例

5
0 1
1 2
2 3
3 2
6 1

输出样例

2