题目描述

农民约翰在他的谷仓里安装了一台新的奇特挤奶机，但它耗电太多，有时会导致电力耗尽！

这种情况经常发生，贝西已经记媛了谷仓的地图，使她更容易在黑暗中找到谷仓的出口。不过，她很好奇断电对她快速离开谷仓的能力的影响。例如，她想知道她可能需要走多远才能在黑暗中找到出口。

仓库由一个简单（非自交）多边形描述，该多边形具有按顺时针顺序列出的整数顶点$\red{（x1，}$$\red{y1）…}$$\red{（xn ，}$$\red{yn）}$。其边缘在水平（平行于$\red{x}$轴）和垂直（平行于$\red{y}$轴）之间交替；第一条边可以是任何一种类 型。出口位于$\red{（x1，}$$\red{y1）}$。贝西从位于某个顶点$\red{(xi,yi)}$的谷仓内开始，$\red{i>1}$。她只能绕着谷 仓的周边走，无论是顺时针还是逆时针，当她到达顶点时，可能会改变方向。她的目标是走最短的距离才能到达出口。

当然，这是相对容易做到的，因为她将从当前位置顺时针或逆时针行驶到出口--无论哪个方向更短。

一天，灯灭了，贝西惊慌失措，忘记了她站在哪个顶点。

幸运的是，她仍然记得谷仓的准确地图，因此她可以通过四处走动和使用触觉来确定自己的位置。每当她站在一个顶点（包括她的初始顶点）时，她可以感觉到是左转还是右转，并且她可以判断该顶点是否是出口。当她沿着谷仓的边缘行走时，她可以在沿着整个边缘行走后确定边缘的确切长度。

一般来说，贝西会有策略地在起点周围摸索，直到她知道足够的信息来确定自己在哪里，在这一点上，她可以很容易地找出如何通过最小的剩余距离到达出口。

假设贝西在每种情况下都按照最优策略移动，请帮助她确定在黑暗中旅行与在有灯光的谷仓中旅行的最坏情况下（在所有可能的情况下，她的起始顶点）她旅行距离增加的最猩能量。

对于未照明情况的"最佳"策略是将这种额外的最坏情况量最小化。

输入格式

输入的第一行包含$\red{N（}$$\red{4≤}$$\red{N≤}$$\red{200). }$

接下来的每一条神经网络线都包含两个整数，以顺时针方向围绕仓库描述点$\red{（xi，}$$\red{yi）}$。

这些整数在（$\red{100,000…}$$\red{100,000}$）

输出格式

请输出贝西在黑暗中的最佳距离比她在有灯光的谷仓中的最佳距离长的最猩能最坏情况量

其中最坏情况是贝西可以开始的所有可能顶点。

样例

输入样例

4
0 0
0 10
1 10
1 0

输出样例

2

提示

在这个例子中，贝西可以感觉到她最初站在一个向内弯曲的地方。

然而，因为在这个例子中，所有的角落都是向内弯曲的，这告 诉了她很少的信息。

一个最佳策略是顺时针行驶。

这是最佳的，她从顶点$\red{3}$或$\red{4}$开始，如果她从顶点$\red{2}$开始，则只增加$\red{2}$个单位的距离。