문제

민용이는 동아리방에 새로운 자동화 기기를 설치했다. 하지만 이 기기는 전력을 너무 많이 소모해서 가끔 동아리방 전체의 전원이 나가기도 한다! 정전이 너무 자주 발생한 나머지, 민용이는 어둠 속에서도 출구를 쉽게 찾을 수 있도록 동아리방의 지도를 완전히 외워버렸다. 민용이는 정전이 발생했을 때 자신이 출구까지 얼마나 빨리 나갈 수 있을지 궁금해졌다. 구체적으로, 불이 꺼져 있을 때 출구를 찾기 위해 불이 켜져 있을 때보다 얼마나 더 많이 걸어야 하는지 알고 싶다.

동아리방은 시계 방향 순서로 나열된 정수 좌표 정점 $(x_1, y_1), \ldots, (x_n, y_n)$으로 이루어진 단순 다각형(자기 교차하지 않는 다각형)으로 묘사된다. 모든 변은 수평(x축에 평행)하거나 수직(y축에 평행)하며, 첫 번째 변은 어느 쪽이든 될 수 있다. 출구는 $(x_1, y_1)$에 위치한다. 민용이는 시작할 때 $i > 1$인 어떤 정점 $(x_i, y_i)$에 서 있다. 민용이는 동아리방의 외곽(변)을 따라서만 이동할 수 있으며, 시계 방향 또는 반시계 방향으로 걸을 수 있다. 정점에 도달할 때마다 방향을 바꿀 수도 있다. 민용이의 목표는 출구까지 최소 거리로 이동하는 것이다. 불이 켜져 있다면 현재 위치에서 시계 방향과 반시계 방향 중 더 짧은 쪽을 선택하면 되므로 이 문제는 매우 간단하다.

어느 날 불이 나갔고, 당황한 민용이는 자신이 어느 정점에 서 있는지 잊어버렸다. 다행히 민용이는 지도를 정확히 기억하고 있으므로, 외곽을 따라 걸으며 촉감을 이용해 자신의 위치를 파악할 수 있다. 민용이는 어떤 정점(시작 정점 포함)에 서 있을 때마다, 그 정점이 좌회전하는 곳인지 우회전하는 곳인지 알 수 있으며, 그곳이 출구인지도 알 수 있다. 또한 동아리방의 변을 따라 걷는 동안에는, 변 전체를 다 걷고 난 후 그 변의 정확한 길이를 알 수 있다. 민용이는 자신이 어느 정점에 있는지 확신할 수 있을 만큼 충분한 정보를 얻을 때까지 전략적으로 시계 방향으로 이동한다. 자신의 위치를 확신하는 즉시, 민용이는 남은 거리 동안 최단 경로로 출구까지 이동한다.

모든 가능한 시작 정점에 대하여, 불이 꺼졌을 때 민용이가 이동하는 거리가 불이 켜져 있을 때의 최단 거리보다 얼마나 더 길어지는지 계산할 수 있다. 민용이가 최적의 전략을 사용한다고 가정할 때, 이 증가량의 최댓값을 구하시오.

입력

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

이어서 $N$개의 줄에 걸쳐 동아리방의 정점 좌표 $(x_i, y_i)$가 시계 방향 순서대로 주어진다. 각 좌표는 $-100\,000$ 이상 $100\,000$ 이하의 정수이다.

출력

모든 가능한 시작 정점에 대해, 불이 꺼졌을 때 민용이의 최적 전략에 따른 이동 거리가 불이 켜졌을 때의 최단 거리보다 길어지는 정도를 구한다. 그 값들 중 최댓값을 출력한다.

예제 입력 1

4
0 0
0 10
1 10
1 0

예제 출력 1

2