← 返回题目列表

Codeforces · 137/C

C. 历史

中文机器翻译题面 查看原题

Polycarpus非常喜欢在学校学习,他总是认真做作业。波利卡普斯在自然科学方面从来没有遇到过任何问题,因为他的曾曾祖父是伟大的物理学家塞恩斯坦。但另一方面,波利卡普斯在历史上却从未有过轻松的时光。

大家都知道,世界历史恰好包含 n 个事件:第 i 个事件从 ai 年持续到 bi 年(含 ai < bi)。波利卡普斯很容易就知道了 n 个事件中每一个事件开始和结束的日期(波利卡普斯从他的曾曾祖父那里继承了出色的记忆力)。但老师给了他一个更复杂的任务:波利卡普洛斯应该知道所有事件何时开始和结束,并且他还应该找出每个事件是否包含另一个事件。 Polycarpus 的老师认为如果 aj < ai 且 bi < bj,则事件 j 包含事件 i。您的任务更简单:查找某些其他事件中包含的事件数。

输入

第一个输入行包含整数 n (1 ≤ n ≤ 105),表示事件的数量。接下来的 n 行包含历史事件的描述,每行一个事件。第 i + 1 行包含两个整数 ai 和 bi (1 ≤ ai < bi ≤ 109) — 第 i 个事件的开始和结束。没有两个事件在同一年开始或结束,即,对于所有 i、j(其中 i ≠ j),ai ≠ aj、ai ≠ bj、bi ≠ aj、bi ≠ bj。事件以任意顺序给出。

输出

打印唯一的整数——问题的答案。

示例

输入 #1

5
1 10
2 9
3 8
4 7
5 6

输出 #1

4

输入 #2

5
1 100
2 50
51 99
52 98
10 60

输出 #2

4

输入 #3

1
1 1000000000

输出 #3

0

注意

在第一个示例中,第五个事件包含在第四个事件中。同样,第四个事件包含在第三个事件中,第三个事件包含在第二个事件中,第二个事件包含在第一个事件中。

在第二个示例中,除了第一个事件之外的所有事件都包含在第一个示例中。

在第三个示例中只有一个事件,因此答案为 0。