两位经验丰富的登山者正计划进行一次前所未有的尝试：他们从山脉中海拔相同的两个点出发，在一条单一的路线上来回移动，同时保持两人的海拔高度始终相同，并最终在路线上的某一点相遇。一位智者告诉他们，如果路线上没有比起点（海拔相同）更低的点，那么至少存在一种方法可以完成这一尝试。这就是这两位登山者敢于开始计划这一奇妙尝试的原因。

两位登山者已经配备了高度计（显示海拔的设备）和保持两人海拔相同所需的通信设备。他们还选择了一条候选路线：该路线由连续且无分支的线段组成；两个起点位于路线的两端；路线上没有比这两个海拔相同的起点更低的点。图 E.1 展示了该路线的示意图（该图对应于样例输入中的第一个数据集）。

图 E.1：路线示意图

正如智者所说，对于这条路线，这种尝试应该是可行的。然而，这两位登山者无法找到一组移动序列来完成这一尝试，因为如果不进行前进和后退的复杂组合，他们就无法保持海拔高度相同。例如，对于上图所示的路线：从 $p_1$ 出发的登山者（设为 A）移动到 $s$，而另一个登山者（设为 B）从 $p_6$ 移动到 $p_5$；接着 A 退回到 $t$，同时 B 移动到 $p_4$；最后 A 到达 $p_3$，同时 B 也到达 $p_3$。实际情况可能会复杂得多，因此他们请求你编写一个程序来为他们找到一组移动序列。

可能存在多组可行的移动序列，因此你需要找到总长度（两人的移动距离之和）最短的那组移动序列。这里，我们沿着路线表面测量长度，例如，从 $(0, 0)$ 到 $(3, 4)$ 的上坡路径长度为 $5$。

输入格式

输入包含多个数据集。

每个数据集的第一行包含一个整数 $N$（$2 \le N \le 100$），表示路线上的点数。 接下来的 $N$ 行，每行包含一个点的坐标 $(x_i, y_i)$（$i = 1, 2, \dots, N$）：两个起点分别为 $(x_1, y_1)$ 和 $(x_N, y_N)$；路线的线段连接 $(x_i, y_i)$ 和 $(x_{i+1}, y_{i+1})$（对于 $i = 1, 2, \dots, N - 1$）。这里，$x_i$ 是沿路线距离起点 $x_1$ 的水平距离，$y_i$ 是相对于起点 $y_1$ 的海拔高度。所有坐标均为小于 $1000$ 的非负整数，且对于 $i = 1, 2, \dots, N - 1$，满足不等式 $x_i < x_{i+1}$，并且对于 $i = 2, 3, \dots, N - 1$，满足 $0 = y_1 = y_N \le y_i$。

输入结束由仅包含一个零的行表示。

输出格式

对于每个数据集，输出两名登山者在路线上某点相遇之前，移动序列的最小长度之和（沿路线测量）。每个输出值与真实值的误差不得超过 $0.01$。

样例

输入 1

6
0 0
3 4
9 12
17 6
21 9
33 0
5
0 0
10 0
20 0
30 0
40 0
10
0 0
1 2
3 0
6 3
9 0
11 2
13 0
15 2
16 2
18 0
7
0 0
150 997
300 1
450 999
600 2
750 998
900 0
0

输出 1

52.5
40.0
30.3356209304689
10078.072814085803