다각형 나라의 경비원

당신은 다각형 나라 국방부의 IT 시스템 관리자다.

다각형 나라의 국경은 꼭짓점이 $N$개인 다각형이다. 2차원 평면에 그리면 모든 꼭짓점은 격자점 위에 있고, 모든 변은 $x$축이나 $y$축과 평행하다.

적의 침입을 막으려고 국경을 따라 아주 튼튼한 방어벽을 세웠다. 그런데 꼭짓점은 벽과 벽이 만나는 자리라서 구조적으로 약한 부분이 생기고, 이 약점은 없앨 수 없다. 그래서 적은 꼭짓점을 노려 침입하기도 한다.

국방부는 꼭짓점을 감시해 침입을 되도록 빨리 알아내려고 경비원을 고용하기로 했다. 경비원은 꼭짓점 위에만 배치하며, 모든 꼭짓점이 적어도 한 명에게 감시되도록 배치한다. 꼭짓점 $A$에 선 경비원은 $A$와 $B$를 잇는 선분 전체가 다각형 내부에 있거나 변 위에 있으면 꼭짓점 $B$를 감시할 수 있다. 물론 경비원은 자신이 선 꼭짓점도 감시한다. 한 경비원은 자신이 감시할 수 있는 꼭짓점을 모두 동시에 감시한다.

국방부는 방어 비용을 줄이려고 경비원 수를 최소로 하고 싶다. 모든 꼭짓점을 감시하는 데 필요한 경비원의 최소 인원을 구하라.

입력 형식은 다음과 같다.

N
X1 Y1
:
:
XN YN

첫째 줄에 짝수 $N$이 주어진다 ($4 \le N < 40$).

이어지는 $N$개 줄에 다각형의 꼭짓점을 준다. 각 줄에는 정수 $X_i$와 $Y_i$가 공백 하나를 사이에 두고 주어진다 ($1 \le i \le N$, $\lvert X_i \rvert \le 1000$, $\lvert Y_i \rvert \le 1000$). $i$번째 꼭짓점의 위치는 $(X_i, Y_i)$다.

$i$가 홀수면 $X_i = X_{i+1}$이고 $Y_i \ne Y_{i+1}$이다. $i$가 짝수면 $X_i \ne X_{i+1}$이고 $Y_i = Y_{i+1}$이다. 여기서 $X_{N+1} = X_1$, $Y_{N+1} = Y_1$로 본다.

꼭짓점은 $x$축이 오른쪽, $y$축이 위를 향하는 좌표계에서 반시계 방향으로 주어진다. 다각형은 단순하다. 즉 각 변은 이웃한 변과 끝점을 공유하는 것 말고는 다른 변과 어떤 점도 공유하지 않는다.

모든 꼭짓점을 감시하는 데 필요한 경비원의 최소 인원을 한 줄에 출력한다.