Wowo's Cheating Run

Wowo is a solitary adventurer invited to test a new running trial at the Shanghai ICPC. The trial is a 2D simple polyline represented by points \(p_1, p_2, \ldots, p_n\) and consists of \(n-1\) line segments \((p_1,p_2), (p_2,p_3), \ldots,(p_{n-1},p_n)\). It is guaranteed that the segments do not intersect except at consecutive endpoints and that any two consecutive segments have different directions.

Wowo must run from \(p_1\) to \(p_n\) along the given order. However, he can choose two points \(a\) and \(b\) on the trial (each either a vertex \(p_i\) or a point on a segment \((p_i, p_{i+1})\)) and use his smart device to run directly from \(a\) to \(b\) in a straight line. Before reaching \(a\) and after reaching \(b\), he runs along the original polyline. To avoid detection, the direct segment \((a, b)\) must not intersect or even touch any segment of the trial except at \(a\) and \(b\).

Your task is to help Wowo choose such points (you may assume the endpoints are chosen among the vertices \(p_1, p_2, \ldots, p_n\)) so that the total running distance is minimized. In other words, if Wowo chooses vertices \(p_i\) and \(p_j\) (with \(1 \le i < j \le n\)) as his cheat endpoints, his running distance will be:

\[ D = \text{dist}(p_1, p_i) + \|p_i-p_j\| + \text{dist}(p_j, p_n), \]

where \(\text{dist}(p_1, p_i)\) and \(\text{dist}(p_j, p_n)\) are the distances along the original trial (i.e. the sum of Euclidean distances of consecutive segments along the path) and \(\|p_i-p_j\|\) is the Euclidean distance between \(p_i\) and \(p_j\). The cheat edge \((p_i, p_j)\) is allowed only if the straight line connecting \(p_i\) and \(p_j\) does not intersect or touch any trial segment other than at \(p_i\) and \(p_j\>.

If no beneficial cheat is possible, Wowo may simply run along the original trial. Output the minimum possible running distance.

inputFormat

The first line contains an integer \(n\) (\(2 \le n \le 1000\)) representing the number of vertices on the polyline.

Each of the next \(n\) lines contains two integers \(x\) and \(y\) (\(|x|,|y| \le 10^4\)) representing the coordinates of the vertex \(p_i\) in order from \(p_1\) to \(p_n\).

outputFormat

Output a single real number — the minimum running distance required. The answer is considered correct if its absolute or relative error does not exceed \(10^{-6}\).

sample

4
0 0
1 0
1 1
0 1

1.000000