30860번 - Product Delivery 다국어

문제

There is only one railway line connecting $(n + 1)$ cities developed along the coastline. When cities along the coast are sequentially identified by numbers between 0ドル$ and $n,ドル city $(i - 1)$ and city $i$ (1ドル ≤ i ≤ n$) are connected by rail, but other cities are not connected by rail.

Since every city except city 0ドル$ is famous as a tourist destination, every city $i$ (1ドル ≤ i ≤ n$) excluding city 0ドル$ is preparing a variety of goods to welcome travelers ahead of the tourist season. Worldwide famous goods BFB is the most popular item in every city. However, the supplier of this product is located in city 0ドル$.

There is only one store that sells BFB in each city $i$ (1ドル ≤ i ≤ n$). Let $S_i$ be the BFB specialty store in city $i$. In each $S_i,ドル the number of BFBs expected to be sold in the tourist season is analyzed and reported to the supplier in the form of $[l_i, m_i]$. Here, $l_i$ and $m_i$ represent the minimum and the maximum number of expected required products, respectively.

The BFB supply company in city 0ドル$ collects request information from stores in every city and supplies products according to the rules described below.

• Select a city, say city $k$ (1ドル ≤ k ≤ n$). Then, take a train departing from city 0ドル,ドル travel to city $k,ドル and supply BFBs only to the stores along the route. In other words, the BFB supplier supplies products to $S_1, S_2, \dots , S_k$.
• Let $c_i$ be the number of BFBs supplied to $S_i$ (1ドル ≤ i ≤ k$) while moving along the route, the condition $c_i ≤ c_{i+1}$ (1ドル ≤ i ≤ k - 1$) must be satisfied.

If the supplier supplies products according to the supply rules described above, it may be impossible for every store to supply the desired number of items with a single supply procedure. Therefore, the supplier must go through several supply procedures to deliver the products but must comply with the supply rules described above each time. After completing all supply procedures, each $S_i$ will have at least $l_i$ and at most $m_i$ items.

For example, suppose $n = 4$ and the number of items required by each store $S_i$ (1ドル ≤ i ≤ 4$) are $[13,15],ドル $[5,8],ドル $[6,14],ドル and $[3,7],ドル respectively. In order for each store to supply the desired quantity of goods, there must be at least two delivery procedures. In the first delivery procedure, 6ドル$ items can be supplied to each of the 4ドル$ stores. Once delivery is completed in this first procedure, all stores' requests except $S_1$ are satisfied. Since 6ドル$ items have already been delivered to $S_1,ドル $r$ (7ドル ≤ r ≤ 9$) additional products will be delivered to $S_1$ in the second delivery procedure. Of course, there may be other delivery methods. However, at least two delivery procedures are required.

Write a program to calculate the minimum number of supply procedures in order to supply the number of BFBs required by each store according to the above rules.

입력

Your program is to read from standard input. The input starts with a line containing an integer $n$ (1ドル ≤ n ≤ 10^6$), where $n$ is the number of cities in which the BFB specialty stores locate. In the following $n$ lines, the $i$-th line contains two integers $l_i$ and $m_i$ (1ドル ≤ l_i ≤ m_i ≤ 10^9$) which indicate the minimum and the maximum number of expected required products by $S_i$.

출력

Your program is to write to standard output. Print exactly one line. The line should contain the minimum number of supply processes in order to supply the number of products required by each store according to the delivery rules.

제한

힌트