불 꺼진 헛간

농부 존이 헛간에 새 착유기를 들여놓았다. 전력을 너무 많이 먹어서 가끔 불이 나간다. 베시는 헛간 지도를 외워 두었기 때문에 어두워도 출구까지 갈 수 있는데, 어둠 때문에 얼마나 더 걷게 되는지 알고 싶어 한다.

헛간은 꼭짓점이 $N$개인 단순 다각형이고, 정수 좌표 꼭짓점 $(x_1, y_1), \ldots, (x_N, y_N)$이 시계 방향으로 주어진다. 경계는 자기 자신과 닿지도 교차하지도 않는다. 변은 가로와 세로가 번갈아 나오며, 첫 변은 둘 중 어느 쪽이어도 된다. 출구는 $(x_1, y_1)$에 있다. 베시는 $i > 1$인 꼭짓점 $(x_i, y_i)$에 서 있고, 자기가 출구에 서 있지 않다는 것은 안다.

베시는 둘레를 따라서만 걷는다. 도착한 꼭짓점에서 언제든 돌아설 수 있으므로 시계 방향으로도 반시계 방향으로도 갈 수 있다. 지도를 알고 있어서 벽을 따라가는 두 방향 중 어느 쪽이 시계 방향인지 항상 안다.

불이 켜져 있으면 자기가 선 꼭짓점을 아니까 시계 방향과 반시계 방향 중 더 짧은 쪽으로 출구까지 간다.

불이 꺼지면 자기가 어느 꼭짓점에 서 있는지 잊는다. 지도는 그대로 기억하고, 움직이면서 다음 정보를 얻는다.

• 출발한 꼭짓점을 포함해 어느 꼭짓점에 서 있든, 그 자리의 헛간 내각이 90도인지 270도인지 느낀다.
• 어느 꼭짓점에 서 있든 그 꼭짓점이 출구인지 아닌지 느낀다.
• 변 하나를 끝까지 걸으면 그 변의 길이를 정확히 안다.

베시는 모은 정보로 출발 꼭짓점이 딱 하나로 좁혀질 때까지 걷는다. 그 순간부터는 자기가 걸어온 자리를 모두 알게 되므로, 지금 선 자리에서 더 짧은 쪽으로 출구까지 간다. 어두울 때의 이동 거리는 위치를 알아내는 동안 걸은 거리와 마지막 이동 거리를 더한 값이다.

어둠 속에서 쓸 전략을 하나 정하자. 출발 꼭짓점이 $i$일 때 그 전략이 걷게 하는 거리를 $d_i$, 불이 켜져 있을 때 걷는 거리를 $s_i$라 하자. 이 전략의 비용은 $\max_{i > 1} (d_i - s_i)$이다. 모든 전략 중 비용의 최솟값을 구하라.

첫 줄에 $N$이 주어진다 ($4 \le N \le 200$).

다음 $N$개 줄에는 헛간 둘레를 시계 방향으로 도는 순서대로 꼭짓점 좌표 $x_i$와 $y_i$가 정수로 주어진다. 모든 좌표는 $-100000$ 이상 $100000$ 이하이다.

어둠 속 전략의 비용 중 최솟값을 정수 하나로 출력한다.