问题描述

你是Polygon国防部的IT系统管理员。

Polygon国的边界形成了一个具有 $N$ 个顶点的多边形。在二维平面上，它的所有顶点都在格点上，并且其所有边都与$x$轴或$y$轴平行。

为了防止敌人入侵该国，该国边界上建造了非常坚固的防御墙。然而，在顶点处，墙壁的连接点存在无法避免的结构性弱点。因此，敌人可能会从顶点处发动攻击和入侵。

为了尽快观察顶点并发现敌军入侵，该部决定雇佣一些守卫。该部计划将他们部署在一些顶点上，以便所有顶点都至少被一个守卫观察到。如果顶点$A$上有一个守卫，则守卫可以观察到顶点$B$，前提是连接$A$和$B$的整个线段在Polygon国内或在其边界上。当然，守卫可以观察自己所在的顶点。一个守卫可以同时观察到他或她能够观察到的所有顶点。

为了减少防御费用，该部希望最小化守卫的数量。你的任务是计算观察到多边形国所有顶点所需的最小守卫数量。

输入

输入格式如下。

$N$
$X\_1$ $Y\_1$
:
:
$X\_N$ $Y\_N$

第一行包含一个偶数$N$ ($4 \le N < 40$)。接下来的$N$行描述了Polygon国的顶点。每行包含两个整数$X\_i$和$Y\_i$ ($1 \le i \le N$, $|X\_i| \le 1{,}000$, $|Y\_i| \le 1{,}000$)，用一个空格分隔。第$i$个顶点的位置是$(X\_i,Y\_i)$。

如果$i$是奇数，则$X\_i = X\_{i+1}$，$Y\_i \ne Y\_{i+1}$。否则，$X\_i \ne X\_{i+1}$，$Y\_i = Y\_{i+1}$。在此，我们认为$X\_{N+1} = X\_1$，$Y\_{N+1} = Y\_1$。顶点按照逆时针顺序给出，坐标系下$x$轴向右，$y$轴向上。Polygon国的形状是简单的。也就是说，除了与相邻边共享端点之外，每条边不与其他边共享任何点。

输出

在一行中打印最小守卫数量。

示例输入1

8
0 2
0 0
2 0
2 1
3 1
3 3
1 3
1 2```

### 示例输出1

```plain
1```

* * *

### 示例输入2

```plain
12
0 0
0 -13
3 -13
3 -10
10 -10
10 10
-1 10
-1 13
-4 13
-4 10
-10 10
-10 0```

### 示例输出2

```plain
2```

* * *

### 来源

[Japan Alumni Group Spring Contest 2014](http://acm-icpc.aitea.net/index.php?2013%2FPractice%2F%BD%D5%A5%B3%A5%F3%A5%C6%A5%B9%A5%C8%2F%B0%C6%C6%E2)

* * *