You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在Z星球的日历中，2026年竟然有惊人的2026天，我们把每一天从 1 到 2026 编号。

小Z立下目标：这一年要尽可能多地参加编程比赛。

小Z一共收集到了 $n$ 场比赛的时间安排信息，第 $i$ 场比赛在第 $l_i$ 天开始，在第 $r_i$ 天结束（含首尾两天），并且如果小Z选择参加某一场比赛，就必须从头打到尾，不能只参加一部分。

小Z在任意一天最多只能参加一场比赛，也就是说，如果两场比赛的时间区间有重叠（哪怕只重叠一天），小Z就不能同时参加它们俩。

小Z想知道，在 2026 年，他最多可以参加多少场比赛？

输入格式

第一行一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示比赛数量。

接下来 $n$ 行，每行两个整数 $l_i, r_i$（$1 \le l_i \le r_i \le 2026$），表示第 $i$ 场比赛的开始和结束日期（包含两端）。

输出格式

输出一个整数，表示小Z最多能参加的比赛数量。

输入输出样例 #1

输入 #1

4
1 3
3 5
5 7
2 4

输出 #1

2

输入输出样例 #2

输入 #2

3
1 10
5 15
20 30

输出 #2

2

说明/提示

样例1：

比赛区间有：[1,3]、[3,5]、[5,7]、[2,4]

注意，区间 [1,3] 和 [3,5] 在第 3 天重叠，因此不能一起参加；

一种最优方案是参加 [1,3] 和 [5,7]，或 [2,4] 和 [5,7]，最多参加 2 场。

样例2：

如果参加第 1 场（1–10 日）和第 3 场（20–30 日），总共参加 2 场比赛；

第 1 场和第 2 场比赛时间重叠（5–10 日），不能同时参加；

第 2 场和第 3 场也可一起参加，也是 2 场。

无论怎么选，最多都只能参加 2 场比赛。