Farmer John 在牛棚裡安裝了一台豪華的新擠奶機，但它耗電太大，偶爾會造成停電！這種情況經常發生，Bessie 已背下牛棚的地圖，以便在黑暗中找到出口。不過，她好奇停電會怎樣影響快速離開牛棚的能力。例如，她想知道在黑暗中尋找出口可能要多走多少路。

牛棚由一個簡單（不自交）多邊形描述，整數座標頂點 $(x_1, y_1) \ldots (x_n, y_n)$ 依順時針順序列出。邊交替為水平（平行於 $x$ 軸）和垂直（平行於 $y$ 軸），第一條邊可以是任一種。出口位於 $(x_1, y_1)$。Bessie 開始時在牛棚的某個頂點 $(x_i, y_i)$，其中 $i > 1$。她只能沿周界順時針或逆時針行走，目標是以最短距離到達出口。開燈時這很容易：從目前位置到出口，哪個方向較短就走哪個方向。

一天，燈熄滅了，Bessie 慌亂中忘記自己站在哪個頂點。幸好她仍記得牛棚的精確地圖，可以透過行走和觸摸判斷位置。每當她站在頂點（包括初始頂點）時，可以觸摸感知其精確內角，並判斷它是否是出口。沿一條邊走完整條邊之後，她能夠確定其精確長度。Bessie 決定採用以下策略：沿牛棚周界順時針走，直到觸摸到足夠的角和邊，推斷出目前所在頂點。此時她可以輕鬆確定到出口的最短剩餘路線，繼續順時針走或轉向逆時針走。

請幫 Bessie 確定：在所有可能的起始頂點中，最壞情況下，黑暗中與開燈時相比，行走距離最多增加多少。

輸入格式

輸入第一行包含 $N$ ($4 \leq N \leq 200$)。接下來 $N$ 行每行包含兩個整數，依順時針順序描述牛棚的頂點 $(x_i, y_i)$。這些整數在範圍 $-100,000 \ldots 100,000$ 內。

輸出格式

輸出採用題述策略時，在最壞起始位置下，Bessie 行走距離的最大增加量。

範例

輸入格式 1

4
0 0
0 10
1 10
1 0

輸出格式 1

2

說明

本例中，Bessie 可以感知初始處是一個 90 度角，但無法區分自己位於頂點 2、3 還是 4。沿順時針走完一條邊後，她要麼到達出口，要麼可根據該邊長度唯一確定位置。行走距離如下：

若從頂點 2 開始：黑暗中走 12 單位（走 1 單位到頂點 3，再走 11 單位繼續到出口）。開燈時只需走 10 單位，因此該頂點的額外距離為 2。

若從頂點 3 開始：兩種情況下都走 11 單位。

若從頂點 4 開始：兩種情況下都走 1 單位。

所以所有起始位置的最壞差值為 $12 - 10 = 2$。也就是說，採用該策略，無論從哪裡開始，Bessie 都能保證黑暗中比開燈時最多多走 2 單位距離。

題目作者：Brian Dean