#P5029. 贴小广告

    ID: 4127 传统题 1000ms 256MiB 尝试: 296 已通过: 138 难度: 5 上传者: 标签>CF1700普及+/提高-逆向思考离散化半开区间统一普通并查集路径压缩按大小合并添加哨兵POJ2528

贴小广告

题目描述

现在有一堵墙,墙上分为若干个单元。接下来会来n个人在墙上贴小广告。每次每个人选择墙上连续一段的单元贴

上自己公司与众不同的小广告。因为小广告可能会出现被覆盖的情况,由于公司之间存在竞争,后贴广告的人想让

别人看不见前面公司的广告,所以会将前面的广告完全覆盖。因此对于墙上的某个单元上贴的小广告中只有贴的最

晚的能被看见。现在想要知道n个人依次贴完后,墙上共能看到多少种小广告?

输入格式

输入文件第一行有一个整数 n。

接下来 n 行每行 2 个整数 li、ri,表示这个人在第li个单元到第ri个单元贴了小广告。

1 <= n,m <= 10^5 , 1<=li<=ri<=10^7

输出格式

输出所有人贴完后墙上能看到多少种小广告?

样例

样例输入

5
1 4
2 6
8 10
3 4
7 10

样例输出

4