강판 자르기 2

ISCO(ICPC Steel Company)는 특정 모양의 강판을 사들여 여러 조각으로 자른 뒤 산업 시장에 파는 회사이다. ISCO가 사들이는 강판은 너비가 같은 두 히스토그램으로 이루어진 모양이다. 한쪽 히스토그램을 위아래로 뒤집어 다른 히스토그램의 아래쪽에 용접한다. 이 과정으로 구멍이 없고 모든 변이 수평 또는 수직인 다각형이 만들어진다. 이런 다각형을 histogon이라고 부른다. histogon의 예는 아래 그림과 같다.

조각이 직사각형이면 시장 가격이 훨씬 높아지므로, 강판을 여러 직사각형으로 자르는 것이 바람직하다. 절단은 레이저 절단기로 한다.

한 번의 작업에서 레이저 절단기는 다각형을 지나는 수평 또는 수직 선분을 따라 자를 수 있다. 이 선분은 다각형의 경계와 정확히 두 점에서만 닿아야 하며, 그 두 점이 선분의 양 끝점이다. 자른 뒤 다각형은 자른 경로를 따라 두 개의 작은 다각형으로 나뉜다. 레이저 절단기는 한 작업에서 하나의 다각형에만 작동한다.

레이저 절단기는 사용 비용이 비싸다. 모든 작업이 끝난 뒤 결과로 나온 다각형이 모두 직사각형이 되도록 하는 최소 작업 횟수를 구하라.

첫 줄에 histogon의 너비 $N$이 주어진다. ($1 \le N \le 250\,000$)

다음 $N$개의 줄에 정수 $h\_i$와 $l\_i$가 주어진다. $h\_i$는 뒤집지 않은 히스토그램의 $i$번째 열의 높이이고, $l\_i$는 뒤집은 히스토그램의 $i$번째 열의 높이이다. ($1 \le h\_i, l\_i \le 1\,000\,000$)

모든 결과 다각형이 직사각형이 되도록 하는 레이저 절단기 작업 횟수의 최소값을 정수 하나로 출력한다.