The Two Men of the Japanese Alps

Two experienced climbers are planning a first-ever attempt. They start at two points of equal altitude on a mountain range, move back and forth along a single route while keeping their altitudes equal at every moment, and finally meet each other at one point on the route.

A wise man told them that whenever a route has no point lower than the two starting points (which are at equal altitude), the attempt can always be achieved. This is why the two climbers dare to plan it.

They already have altimeters (devices that show altitude) and communication devices needed to keep their altitudes equal, and they picked a candidate route: it consists of consecutive straight line segments without branches; the two starting points are the two ends of the route; and no point on the route is lower than the two starting points. The figure below illustrates such a route (it corresponds to the first example input).

The attempt is guaranteed to be possible, but the climbers could not find a pair of move sequences by hand, because keeping their altitudes equal generally requires a complex mix of forward and backward moves. For example, on the route above, one valid plan is: climber A starts at p1 and moves to s while climber B moves from p6 to p5; then A moves back to t while B moves to p4; finally A reaches p3 at the very moment B also reaches p3.

More than one valid pair of move sequences may exist, so you must find the pair whose total travelled length is the smallest. Length is measured along the route surface (arc length): for example, an uphill segment from $(0, 0)$ to $(3, 4)$ has length $5$.

The input is a sequence of datasets.

The first line of each dataset contains an integer $N$ ($2 \le N \le 100$), the number of points on the route. Each of the next $N$ lines contains the coordinates $(x_i, y_i)$ for $i = 1, 2, \dots, N$. The two starting points are $(x_1, y_1)$ and $(x_N, y_N)$, and the route is formed by the line segments connecting $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$ for $i = 1, 2, \dots, N-1$.

Here $x_i$ is the horizontal distance measured along the route from the start point $x_1$, and $y_i$ is the altitude relative to the start altitude $y_1$. All coordinates are non-negative integers smaller than $1000$, and they satisfy $x_i < x_{i+1}$ for $i = 1, 2, \dots, N-1$ and $0 = y_1 = y_N \le y_i$ for $i = 2, 3, \dots, N-1$.

The end of the input is indicated by a line containing a single zero.

For each dataset, output the minimum total length (measured along the route) that the two climbers travel while keeping their altitudes equal, until they meet at a common point.

Print the value rounded to exactly two decimal places, one dataset per line.