Castle

A group of explorers looking for treasure found the map of a castle. According to the map, a priceless treasure is hidden in the cellar. The map is drawn on a square grid whose knots (lattice points) have integer coordinates. The bottom-left knot is $(0, 0)$ and the opposite, top-right knot is $(10000, 10000)$.

The floor plan of the castle is a polygon whose sides run along the grid lines. Any two adjacent sides of the polygon are perpendicular, and the boundary is one closed broken line: every vertex belongs to exactly two segments and every other boundary point belongs to exactly one segment. Each grid-line segment that lies inside the polygon, together with the sides of the polygon, forms a corridor of the cellar. Two special knots are marked, one for the entrance and one for the treasure.

Compute the length of the shortest route through the corridors from the entrance to the treasure. The unit of length is the side of a single grid square, so every step of the route follows the grid lines.

The first line contains one integer $n$ ($4 \le n \le 5000$), the number of vertices of the polygon.

Each of the next $n$ lines contains two integers separated by a single space, the coordinates of the next polygon vertex, given in the order in which the vertices appear while walking along the boundary. Every coordinate lies in the range $[0, 10000]$.

The second to last line holds the coordinates of the entrance, and the last line holds the coordinates of the treasure, written in the same format.

Print a single integer, the length of the shortest route from the entrance to the treasure along the corridors.