Polygon Guards

You are an IT system administrator in the Ministry of Defense of Polygon Country.

The border of Polygon Country is a polygon with $N$ vertices. Drawn on the plane, every vertex sits on a lattice point and every edge is parallel to the $x$ axis or the $y$ axis.

To keep enemies out, a very strong defense wall runs along the whole border. A vertex is where two walls meet, so it has a structural weakness that cannot be removed. Enemies therefore attack and invade at the vertices.

To watch the vertices and notice an invasion as early as possible, the ministry decided to hire guards. Guards stand on vertices only, and they are placed so that every vertex is watched by at least one of them. A guard at vertex $A$ can watch vertex $B$ if the whole segment joining $A$ and $B$ lies inside the polygon or on its edges. A guard also watches the vertex he or she stands on. One guard watches every vertex he or she can watch at the same time.

The ministry wants to cut the defense cost, so it wants the number of guards to be as small as possible. Compute the minimum number of guards needed to watch all vertices of Polygon Country.

The input is formatted as follows.

N
X1 Y1
:
:
XN YN

The first line contains an even integer $N$ ($4 \le N < 40$).

Each of the next $N$ lines describes one vertex of the polygon with two integers $X_i$ and $Y_i$ separated by one space ($1 \le i \le N$, $\lvert X_i \rvert \le 1000$, $\lvert Y_i \rvert \le 1000$). The $i$-th vertex is at $(X_i, Y_i)$.

If $i$ is odd, then $X_i = X_{i+1}$ and $Y_i \ne Y_{i+1}$. If $i$ is even, then $X_i \ne X_{i+1}$ and $Y_i = Y_{i+1}$. Here $X_{N+1} = X_1$ and $Y_{N+1} = Y_1$.

The vertices are given in counterclockwise order in the coordinate system where the $x$ axis points right and the $y$ axis points up. The polygon is simple, so an edge shares no point with any other edge except the endpoints it shares with its two neighbors.

Print the minimum number of guards on one line.