가위

Bajtazar는 가위를 샀다. 성능을 시험해 보고 싶어서 근처에 놓여 있던 다각형을 집어 들고, 이를 여러 개의 직사각형으로 자르기로 했다. 이때 자르는 횟수를 최대한 적게 하고 싶다. Bajtazar가 몇 번을 잘라야 하는지 구하라.

다각형은 수직 선분과 수평 선분만으로 이루어져 있다. 가위를 들기 전에 Bajtazar는 다각형 위에 수직 또는 수평 선분을 몇 개 그린다. 각 선분의 두 끝점은 다각형의 경계 위에 있고, 선분의 내부는 다각형의 내부에 들어 있다. 그런 다음 그린 모든 선분을 따라 다각형을 자른다. 자른 횟수는 그린 선분의 개수와 같다. 모든 자르기를 마친 뒤에는 생겨난 모든 조각이 직사각형이어야 한다.

몇 번의 자르기를 한 뒤에는 앞서 그린 선분 중 일부가 이미 잘려 여러 조각으로 나뉘어 있을 수 있다. 하지만 하나의 그린 선분에서 나온 모든 조각을 따라 자르는 것은 한 번의 자르기로 센다. 특히 이는 $2 \times 2$ 크기의 정사각형을 단 두 번의 자르기만으로 $1 \times 1$ 크기의 정사각형 네 개로 나눌 수 있음을 뜻한다(물론 Bajtazar의 목적에 비추어 보면 그렇게 자르는 것은 의미가 없다).

첫째 줄에 다각형의 꼭짓점 개수를 나타내는 정수 $n$ ($4 \le n \le 100000$)이 주어진다. 다음 $n$개의 줄에는 다각형의 꼭짓점이 경계를 따라 나열된 순서대로 하나씩 주어진다. $i$번째 꼭짓점은 그 좌표를 나타내는 정수 쌍 $x_i$, $y_i$ ($-10^9 \le x_i, y_i \le 10^9$)로 표현된다.

다각형의 모든 변은 수직이거나 수평이다. 다각형의 두 변은 경계에서 이웃한 변일 때에만 서로 만나며, 이 경우 두 변의 유일한 공통점은 함께 가지는 꼭짓점이다. 특히 모든 꼭짓점의 좌표는 서로 다르다.

다각형을 여러 직사각형으로 나누기 위해 필요한 자르기의 최소 횟수를 출력한다.

그림은 위 다각형을 두 번의 자르기로 직사각형들로 나누는 몇 가지 방법을 보여 준다.