English · Original
Chinese · Translation
Formal · Original
Leha and Noora decided to go on a trip in the Baltic States. As you know from the previous problem, Leha has lost his car on the parking of the restaurant. Unfortunately, requests to the watchman didn't helped hacker find the car, so friends decided to go hitchhiking.
In total, they intended to visit _n_ towns. However it turned out that sights in _i_\-th town are open for visitors only on days from _l__i_ to _r__i_.
What to do? Leha proposed to choose for each town _i_ a day, when they will visit this town, i.e any integer _x__i_ in interval \[_l__i_, _r__i_\]. After that Noora choses some subsequence of towns _id_1, _id_2, ..., _id__k_, which friends are going to visit, that at first they are strictly increasing, i.e _id__i_ < _id__i_ + 1 is for all integers _i_ from 1 to _k_ - 1, but also the dates of the friends visits are strictly increasing, i.e _x__id__i_ < _x__id__i_ + 1 is true for all integers _i_ from 1 to _k_ - 1.
Please help Leha and Noora in choosing such _x__i_ for each town _i_, and such subsequence of towns _id_1, _id_2, ..., _id__k_, so that friends can visit maximal number of towns.
You may assume, that Leha and Noora can start the trip any day.
## Input
The first line contains a single integer _n_ (1 ≤ _n_ ≤ 3·105) denoting the number of towns Leha and Noora intended to visit.
Each line _i_ of the _n_ subsequent lines contains two integers _l__i_, _r__i_ (1 ≤ _l__i_ ≤ _r__i_ ≤ 109), denoting that sights in _i_\-th town are open for visitors on any day .
## Output
Print a single integer denoting the maximal number of towns, that Leha and Noora can visit.
[samples]
## Note
Consider the first example.
Let's take this plan: let's visit the sight in the second town on the first day, in the third town on the third day and in the fifth town on the fourth. That's would be the optimal answer.
Leha 和 Noora 决定去波罗的海国家旅行。正如上一道题所知，Leha 在餐厅停车场丢失了他的车。不幸的是，向保安求助也没有帮助黑客找到车，因此朋友们决定搭便车。
他们计划总共访问 #cf_span[n] 个城市。然而，他们发现第 #cf_span[i] 个城市中的景点只在从 #cf_span[li] 到 #cf_span[ri] 的日期内对游客开放。
该怎么办？Leha 提议为每个城市 #cf_span[i] 选择一个他们访问该城市的日期，即在区间 #cf_span[[li, ri] 中任选一个整数 #cf_span[xi]。之后，Noora 选择一个城市子序列 #cf_span[id1, id2, ..., idk]，朋友们将访问这些城市，要求这些城市编号严格递增，即对所有从 #cf_span[1] 到 #cf_span[k - 1] 的整数 #cf_span[i]，都有 #cf_span[idi < idi + 1]，同时访问日期也严格递增，即对所有从 #cf_span[1] 到 #cf_span[k - 1] 的整数 #cf_span[i]，都有 #cf_span[xidi < xidi + 1]。
请帮助 Leha 和 Noora 为每个城市 #cf_span[i] 选择一个 #cf_span[xi]，并选择一个城市子序列 #cf_span[id1, id2, ..., idk]，使得朋友们能访问最多的城市数量。
你可以假设 Leha 和 Noora 可以在任意一天开始旅行。
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 3·105])，表示 Leha 和 Noora 计划访问的城市数量。
接下来的 #cf_span[n] 行中，每行包含两个整数 #cf_span[li], #cf_span[ri] (#cf_span[1 ≤ li ≤ ri ≤ 109])，表示第 #cf_span[i] 个城市中的景点在任意一天 #cf_span[li] 到 #cf_span[ri] 之间对游客开放。
请输出一个整数，表示 Leha 和 Noora 能够访问的最大城市数量。
考虑第一个示例。
假设采用如下计划：在第一天访问第二个城市的景点，第三天访问第三个城市的景点，第四天访问第五个城市的景点。这将是最佳答案。
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 3·105])，表示 Leha 和 Noora 计划访问的城市数量。接下来的 #cf_span[n] 行中，每行包含两个整数 #cf_span[li], #cf_span[ri] (#cf_span[1 ≤ li ≤ ri ≤ 109])，表示第 #cf_span[i] 个城市中的景点在任意一天 #cf_span[li] 到 #cf_span[ri] 之间对游客开放。
## Output
请输出一个整数，表示 Leha 和 Noora 能够访问的最大城市数量。
[samples]
## Note
考虑第一个示例。假设采用如下计划：在第一天访问第二个城市的景点，第三天访问第三个城市的景点，第四天访问第五个城市的景点。这将是最佳答案。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of towns.
For each town $ i \in \{1, \dots, n\} $, let $ [l_i, r_i] $ be the interval of days when the sight is open, with $ l_i, r_i \in \mathbb{Z} $, $ 1 \leq l_i \leq r_i \leq 10^9 $.
Let $ x_i \in [l_i, r_i] $ be the day chosen to visit town $ i $.
Let $ I = (i_1, i_2, \dots, i_k) $ be a subsequence of town indices such that $ 1 \leq i_1 < i_2 < \dots < i_k \leq n $, and $ x_{i_1} < x_{i_2} < \dots < x_{i_k} $.
**Constraints**
1. $ 1 \leq n \leq 3 \cdot 10^5 $
2. For all $ i \in \{1, \dots, n\} $: $ 1 \leq l_i \leq r_i \leq 10^9 $
3. For each $ i $, $ x_i \in [l_i, r_i] $
**Objective**
Maximize the length $ k $ of the subsequence $ I $ such that the chosen visit days $ x_{i_1} < x_{i_2} < \dots < x_{i_k} $ are strictly increasing.
API Response (JSON)
{
"problem": {
"name": "D. Hitchhiking in the Baltic States",
"description": {
"content": "Leha and Noora decided to go on a trip in the Baltic States. As you know from the previous problem, Leha has lost his car on the parking of the restaurant. Unfortunately, requests to the watchman didn",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF809D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Leha and Noora decided to go on a trip in the Baltic States. As you know from the previous problem, Leha has lost his car on the parking of the restaurant. Unfortunately, requests to the watchman didn...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Leha 和 Noora 决定去波罗的海国家旅行。正如上一道题所知，Leha 在餐厅停车场丢失了他的车。不幸的是，向保安求助也没有帮助黑客找到车，因此朋友们决定搭便车。\n\n他们计划总共访问 #cf_span[n] 个城市。然而，他们发现第 #cf_span[i] 个城市中的景点只在从 #cf_span[li] 到 #cf_span[ri] 的日期内对游客开放。\n\n该怎么办？Leha 提议为每个城市...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of towns. \nFor each town $ i \\in \\{1, \\dots, n\\} $, let $ [l_i, r_i] $ be the interval of days when the sight is open, with $ l_i, r_i \\in \\...",
"is_translate": false,
"language": "Formal"
}
]
}