A. Wowoear
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Wowo is a solo adventurer who completed many dangerous journeys on his own foot in forests, deserts and even glaciers. The Shanghai ICPC (Shanghai Invitational Contest on Programmable Cheating) committee invited Wowo as a tester of their new running trial.

The trial can be described as a 2D simple polyline $$$(p_1,\ldots, p_n)$$$. In other words, the trial consists of $$$n-1$$$ line segments $$$(p_1, p_2),\ldots, (p_{n-1}, p_n)$$$. The line segments do not intersect with each other except that two consecutive line segments $$$(p_i, p_{i+1})$$$ and $$$(p_{i+1}, p_{i+2})$$$ intersect at the point $$$p_{i+1}$$$. Any two consecutive segments have different directions. The committee wants Wowo to run from $$$p_1$$$ to $$$p_n$$$ along the line segments $$$(p_1,p_2),\ldots, (p_{n-1}, p_n)$$$ in order.

However, Wowo has a smart device that can hack the committee's system for an interval of time. Wowo is able to choose $$$2$$$ points $$$a, b$$$ on the trial and run directly from $$$a$$$ to $$$b$$$ along the line segment $$$(a, b)$$$. Each of these $$$a$$$ and $$$b$$$ can be some $$$p_i$$$ ($$$1\le i\le n$$$) and can be some point on some line segment $$$(p_i, p_{i+1})$$$ ($$$1\le i \lt n$$$) as well. Before reaching $$$a$$$ and after reaching $$$b$$$, Wowo has to run along the original trial. Wowo does not want to be caught cheating, so he decided that the line segment $$$(a, b)$$$ should not intersect or touch any line segment of the trial at any point other than $$$a$$$ and $$$b$$$. Help Wowo to choose $$$a$$$ and $$$b$$$ wisely and output the shortest distance Wowo need to run from $$$p_1$$$ to $$$p_n$$$ using his smart cheating device.

Input

The first line includes a single integer $$$n$$$ indicating the number of points on the running trial ($$$2\le n\le 200$$$).

The $$$i+1$$$-th line ($$$1\le i\le n$$$) contains two integers $$$x$$$ and $$$y$$$ separated by a single space indicating the coordinates of $$$p_i$$$ ($$$-1000\le x, y\le 1000$$$).

It is guaranteed that the line segments do not intersect with each other except that two consecutive line segments $$$(p_i, p_{i+1})$$$ and $$$(p_{i+1}, p_{i+2})$$$ intersect at the point $$$p_{i+1}$$$. In other words, $$$(p_i, p_{i+1})\cap (p_{j}, p_{j+1})=\left\{\begin{array}{cc}\emptyset & i\neq j-1\\ \{p_{j}\} & i = j-1\end{array}\right.$$$ holds for any integers $$$i, j$$$ satisfying $$$1\le i \lt j \lt n$$$. Here $$$(s, t)$$$ represents all points on the line segment from $$$s$$$ to $$$t$$$ including $$$s$$$ and $$$t$$$.

It is guaranteed that each line segment has nonzero length. In other words, $$$p_i\neq p_{i+1}$$$ for any integer $$$i\in [1, n)$$$.

It is guaranteed that adjacent line segments are not collinear. In other words, for any integer $$$i\in [1,n-2]$$$ and any real number $$$\lambda$$$, $$$p_i - p_{i+1}$$$ is not equal to $$$\lambda(p_{i+1}-p_{i+2})$$$.

Output

Output the shortest distance Wowo needs to run. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Example
Input
5
0 0
1 10
2 0
3 10
4 0
Output
22.099751242242