시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB24112210049.505%

문제

Yan Hao has $n$ swords numbered from $1$ to $n$. Sword $i$ has attack $a[i]$ and defence $b[i]$.

Yan Hao thinks that sword $i$ is useless if there exists a different sword $j$ ($j \ne i$) such that $a[i] ≤ a[j]$ and $b[i] ≤ b[j]$. That is, a sword $i$ is useless if the attack and defence of another sword $j$ are both at least as good as that of sword $i$. If a sword is not useless, we say that it is useful.

Two swords are considered equivalent if they have the same attack and same defence. It is guaranteed that no pair of swords are equivalent.

Help Yan Hao find the number of useful swords in his collection.

입력

The first line of input contains exactly $1$ integer, $n$.

The next $n$ lines of input contains two space-separated integers each. The $i$-th such line of input will contain $a[i]$ and $b[i]$ respectively, indicating the attack and defence of sword $i$.

출력

The output should contain one integer, the number of useful swords.

제한

  • $1 ≤ n ≤ 100\,000$
  • $1 ≤ a[i], b[i] ≤ 10^9$
  • For all $1 ≤ i < j ≤ n$, $a[i] \ne a[j]$ or $b[i] \ne b[j]$

서브태스크

번호배점제한
111

$n ≤ 500$

221

$a[i], b[i] ≤ 500$

334

$a[i] = i$

425

$a[i] \ne a[j]$ for every $1 ≤ i < j ≤ n$

59

No additional constraints

예제 입력 1

3
2 3
1 3
5 3

예제 출력 1

1

Comparing sword $1$ with sword $3$, we have $a[1] = 2 ≤ 5 = a[3]$ and $b[1] = 3 ≤ 3 = b[3]$, so sword $1$ is useless.

Comparing sword $2$ with sword $1$, we have $a[2] = 1 ≤ 2 = a[1]$ and $b[2] = 3 ≤ 3 = b[1]$, so sword $2$ is useless.

Sword $3$ is the only useful sword.

예제 입력 2

4
5 6
2 5
6 9
1 3

예제 출력 2

1

채점 및 기타 정보

  • 예제는 채점하지 않는다.