题目描述

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

这种情况经常发生，贝西已经记住了谷仓的地图，使她更容易在黑暗中找到谷仓的出口。

不过，她很好奇断电对她快速离开谷仓的能力的影响。

例如，她想知道她可能需要走多远才能在黑暗中找到出口。

仓库由一个简单（非自交）多边形描述，该多边形具有按顺时针顺序列出的整数顶点$\red{（x1，}$$\red{y1）…}$$\red{（xn，}$$\red{yn）}$。其边缘在水平（平行于$\red{x}$轴）和垂直（平行于$\red{y}$轴）之间交替；第一条边可以是任何一种类型。出口位于$\red{（x1，}$$\red{y1）}$。

贝西从位于某个顶点$\red{(xi,yi)}$的谷仓内开始，$\red{i>1}$。她只能绕着谷仓的周边走，无论是顺时针还是逆时针，她的目标是 走最短的距离才能到达出口。

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

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

幸运的是，她仍然记得谷仓的准确地图，因此她可以通过四处走动和使用触觉来确定自己的位置。

每当她站在一个顶点（包括她的初始顶点）时，她都能感觉到该顶点的确切内角，并能判断该顶点是否为出口。

当她沿着谷仓的边缘行走时，她可以在沿着整个边缘行走后确定边缘的确切长度。

贝西决定了以下策略：她将沿着谷仓的周长顺时针移动，直到她感觉到足够的角度和边缘来推断她当前所在的顶点。

在这一点上，她可以通过继续顺时针移动或切换方向并逆时针移动，轻松找出如何通过最小剩余距离到达出口。

请帮助贝西确定在黑暗中旅行与在有灯光的谷仓中旅行，在最坏的情况下（在所有可能的情况下，她的起始顶点）她的旅行距离将增加的最大量。

输入格式

输入的第一行包含$\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{90}$度角站立的，但她无法判断她最初是站在顶点$\red{2}$、$\red{3}$还是$\red{4}$。

在顺时针方向沿着一条边缘迈出一步后，贝西要么到达出口，要么可以根据该边缘的长度唯一地确定她的位置。

她获得的距离是：如 果从顶点$\red{2}$开始：她在黑暗中移动$\red{12}$个单位（$\red{1}$个单位到达顶点$\red{3，}$然后$\red{11}$个单位继续到出口 ）。

她只需要在一个有灯光的谷仓里旅行$\red{10}$个单位。这是该顶点的额外距离$\red{2}$。如果从顶点$\red{3}$开始：在这两种情况下，她都移动了$\red{11}$个单位。如果从顶点$\red{4}$开始：在这两种情况下，她移动$\red{1}$个单位。因此，所有起点的最坏情况差为$\red{12-10=2}$。

也就是说，贝西可以保证使用她的策略，无论从哪里开始，她在黑暗中的行程最多比在光明中多$\red{2}$个单位。