문제

충남대학교 알고리즘 동아리방에 새로운 전자기기가 들어왔다. 그런데 이 기기는 전력을 너무 많이 소모해서 가끔 정전을 일으키곤 한다! 정전이 너무 자주 발생한 나머지, 가은이는 어둠 속에서도 출구를 쉽게 찾기 위해 동아리방의 지도를 통째로 외워버렸다. 가은이는 정전이 발생했을 때 자신이 얼마나 더 멀리 걸어야 출구에 도달할 수 있을지 궁금해졌다.

동아리방의 구조는 시계 방향 순서대로 나열된 정수 좌표 $(x_1, y_1), \dots, (x_n, y_n)$을 꼭짓점으로 하는 단순 다각형(자기 교차하지 않는 다각형)으로 표현된다. 모든 변은 수평(x축에 평행)하거나 수직(y축에 평행)하며, 인접한 두 변은 서로 수직이다. 출구는 $(x_1, y_1)$에 위치한다. 가은이는 출구가 아닌 어떤 꼭짓점 $(x_i, y_i)$ ($i > 1$)에서 출발하며, 다각형의 경계를 따라서만 시계 방향 또는 반시계 방향으로 이동할 수 있다. 가은이의 목표는 최소 거리로 이동하여 출구에 도달하는 것이다. 불이 켜져 있을 때는 자신의 위치를 알 수 있으므로, 현재 위치에서 출구까지의 시계 방향 거리와 반시계 방향 거리 중 짧은 쪽을 선택해 이동하면 된다.

어느 날 정전이 발생했고, 가은이는 자신이 어느 꼭짓점에 서 있는지 잊어버려 패닉에 빠졌다. 다행히 동아리방의 지도는 정확히 기억하고 있으므로, 경계를 따라 걸으며 자신의 감각을 이용해 현재 위치를 추론하기로 했다. 가은이가 특정 꼭짓점에 서 있을 때(출발 지점 포함), 해당 꼭짓점의 내각을 느낄 수 있으며 그곳이 출구인지도 알 수 있다. 또한 변을 따라 이동하여 다음 꼭짓점에 도달하면, 방금 지나온 변의 길이를 정확히 알 수 있다.

가은이는 다음과 같은 전략을 세웠다. 먼저 자신의 현재 위치를 유일하게 결정할 수 있을 때까지 경계를 따라 시계 방향으로 이동한다. 현재 위치를 확신하는 즉시, 남은 거리 중 출구까지의 최단 거리(시계 방향 혹은 반시계 방향)를 계산하여 이동한다. 만약 이동 중에 출구에 도착한다면 그 즉시 이동을 멈춘다.

모든 가능한 출발 꼭짓점에 대해, 가은이의 전략을 따랐을 때의 이동 거리와 불이 켜져 있을 때의 최단 이동 거리의 차이를 구할 수 있다. 이 차이의 최댓값을 구하시오.

입력

첫째 줄에 꼭짓점의 개수 $N$이 주어진다. ($4 \le N \le 200$)

이어서 $N$개의 줄에 걸쳐 동아리방의 꼭짓점을 시계 방향 순서대로 나타내는 두 정수 $(x_i, y_i)$가 공백으로 구분되어 주어진다. ($-100\,000 \le x_i, y_i \le 100\,000$)

출력

가은이가 문제에 설명된 전략을 사용했을 때, 불이 켜져 있을 때와 비교하여 이동 거리가 늘어날 수 있는 최댓값을 출력한다.

예제 입력 1

4
0 0
0 10
1 10
1 0

예제 출력 1

2