상품 배송

해안선을 따라 놓인 $(n + 1)$ 개의 도시를 잇는 철도 노선은 하나뿐이다. 도시는 해안을 따라 순서대로 $0$부터 $n$까지 번호가 매겨져 있다. 도시 $i-1$과 도시 $i$ ($1 ≤ i ≤ n$)는 철도로 연결되어 있고, 다른 도시끼리는 연결되어 있지 않다.

0번 도시를 제외한 모든 도시는 유명한 관광지이므로, 각 도시 $i$ ($1 ≤ i ≤ n$)는 관광 시즌을 앞두고 방문객을 위한 다양한 상품을 준비하고 있다. 세계적으로 유명한 상품 BFB는 모든 도시에서 가장 인기가 많다. 하지만 이 상품의 공급처는 0번 도시에 있다.

각 도시 $i$ ($1 ≤ i ≤ n$)에는 BFB를 파는 전문 상점 $S_i$가 하나씩 있다. 각 $S_i$에서 관광 시즌에 팔릴 것으로 예상되는 BFB 개수를 분석하여 $[l_i, m_i]$ 형태로 공급처에 보고한다. 여기서 $l_i$는 예상 수요의 최솟값, $m_i$는 최댓값이다.

공급처는 각 도시 상점의 요청 정보를 모아 다음 규칙에 따라 상품을 공급한다.

• 도시 $k$ ($1 ≤ k ≤ n$)를 하나 고른다. 0번 도시에서 기차를 타고 출발해 도시 $k$까지 이동하며, 경로에 있는 상점, 즉 $S_1, S_2, \dots, S_k$에만 BFB를 공급한다.
• 경로를 따라 $S_i$ ($1 ≤ i ≤ k$)에 공급되는 BFB 개수를 $c_i$라 할 때, 조건 $c_i ≤ c_{i+1}$ ($1 ≤ i ≤ k - 1$)을 만족해야 한다.

한 번의 공급으로 모든 상점이 원하는 수량을 받지 못할 수 있다. 따라서 공급처는 위 규칙을 매번 지키면서 여러 번 공급해야 한다. 모든 공급이 끝난 뒤 각 $S_i$가 받은 개수는 $l_i$ 이상 $m_i$ 이하여야 한다.

예를 들어 $n = 4$이고 $S_1$부터 $S_4$까지 필요한 범위가 각각 $[13, 15]$, $[5, 8]$, $[6, 14]$, $[3, 7]$이라고 하자. 최소 두 번의 공급이 필요하다. 첫 번째 공급에서 4개 상점 모두에 6개씩 공급한다. 이 공급이 끝나면 $S_1$을 제외한 모든 상점의 요구가 충족된다. $S_1$은 이미 6개를 받았으므로, 두 번째 공급에서 추가로 $r$ ($7 ≤ r ≤ 9$)개를 받는다. 다른 공급 방법도 가능하지만, 최소 두 번의 공급은 반드시 필요하다.

첫 줄에 BFB 전문 상점이 있는 도시의 수 $n$ ($1 ≤ n ≤ 10^6$)이 주어진다. 이어지는 $n$개의 줄 중 $i$번째 줄에는 $S_i$의 예상 수요의 최솟값 $l_i$와 최댓값 $m_i$ ($1 ≤ l_i ≤ m_i ≤ 10^9$)가 공백으로 구분되어 주어진다.

공급 규칙에 따라 모든 상점의 수요를 맞추는 데 필요한 공급 횟수의 최솟값을 한 줄에 출력한다.