Problem: Two experienced climbers are planning a first-ever attempt: they start at two points of the equal altitudes on a mountain range, move back and forth on a single route keeping their altitudes equal, and finally meet with each other at a point on the route. A wise man told them that if a route has no point lower than the start points (of the equal altitudes) there is at least a way to achieve the attempt. This is the reason why the two climbers dare to start planning this fancy attempt.

The two climbers already obtained altimeters (devices that indicate altitude) and communication devices that are needed for keeping their altitudes equal. They also picked up a candidate route for the attempt: the route consists of consequent line segments without branches; the two starting points are at the two ends of the route; there is no point lower than the two starting points of the equal altitudes. An illustration of the route is given in Figure E.1 (this figure corresponds to the first dataset of the sample input).

<image>

Figure E.1: An illustration of a route

The attempt should be possible for the route as the wise man said. The two climbers, however, could not find a pair of move sequences to achieve the attempt, because they cannot keep their altitudes equal without a complex combination of both forward and backward moves. For example, for the route illustrated above: a climber starting at p1 (say A) moves to s, and the other climber (say B) moves from p6 to p5; then A moves back to t while B moves to p4; finally A arrives at p3 and at the same time B also arrives at p3. Things can be much more complicated and thus they asked you to write a program to find a pair of move sequences for them.

There may exist more than one possible pair of move sequences, and thus you are requested to find the pair of move sequences with the shortest length sum. Here, we measure the length along the route surface, i.e., an uphill path from (0, 0) to (3, 4) has the length of 5.



Input

The input is a sequence of datasets.

The first line of each dataset has an integer indicating the number of points N (2 ≤ N ≤ 100) on the route. Each of the following N lines has the coordinates (xi, yi) (i = 1, 2, ... , N) of the points: the two start points are (x1, y1) and (xN, yN); the line segments of the route connect (xi, yi) and (xi+1, yi+1) for i = 1, 2, ... , N - 1. Here, xi is the horizontal distance along the route from the start point x1, and yi is the altitude relative to the start point y1. All the coordinates are non-negative integers smaller than 1000, and inequality xi < xi+1 holds for i = 1, 2, .. , N - 1, and 0 = y1 = yN ≤ yi for i = 2, 3, ... , N - 1.

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

Output

For each dataset, output the minimum sum of lengths (along the route) of move sequences until the two climbers meet with each other at a point on the route. Each output value may not have an error greater than 0.01.

Example

Input

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


Output

52.5
40.0
30.3356209304689
10078.072814085803

Solution (in CPP):

Solution:
#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>

using namespace std;

#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) (EQ((a).real(),(b).real()) && EQ((a).imag(),(b).imag()))

typedef complex<double> P;
typedef pair<P,P> Edge;
typedef long long ll;

const double PI=4*atan(1.0);
const int MAX_SIZE = 10000;

// 内積
double dot(P a, P b) {
  return (a.real() * b.real() + a.imag() * b.imag());
}
// 外積
double cross(P a, P b) {
  return (a.real() * b.imag() - a.imag() * b.real());
}
// 点cが直線ab上にあるかないか
int is_point_on_line(P a, P b, P c) {
  return EQ( cross(b-a, c-a), 0.0 );
}
// 2直線の直行判定
int is_orthogonal(P a1, P a2, P b1, P b2) {
  return EQ( dot(a1-a2, b1-b2), 0.0 );
}
// 2直線の平行判定
int is_parallel(P a1, P a2, P b1, P b2) {
  return EQ( cross(a1-a2, b1-b2), 0.0 );
}
// 点a,bを通る直線と点cの間の距離
double distance_l_p(P a, P b, P c) {
  return abs(cross(b-a, c-a)) / abs(b-a);
}
// 点a,bを端点とする線分と点cとの距離
double distance_ls_p(P a, P b, P c) {
  if ( dot(b-a, c-a) < EPS ) return abs(c-a);
  if ( dot(a-b, c-b) < EPS ) return abs(c-b);
  return abs(cross(b-a, c-a)) / abs(b-a);
}
// 点が多角形の中に存在するかどうか
bool isInPolygon(vector<P> &points,P s){
	if(points.size()==1)return false;
	vector<P> v;
	for(int i=0;i<(int)points.size();i++)v.push_back(points[i]-s);
	int sign=0;
	for(int i=1;i<=(int)v.size();i++){
		int prv=(i-1+v.size())%v.size();
		int cur=i%v.size();
		double c=cross(v[prv],v[cur]);
		if(EQ(c,0))continue;
		else if(sign==0){
			if(c>0)sign=1;
			else sign=-1;
		}
		else{
			if(sign==-1&&c>0)return false;
			else if(sign==1&&c<0)return false;
		}
	}
	return true;
}
struct Rec{
	vector<P> p;
};
// a1,a2を端点とする線分とb1,b2を端点とする線分の交差判定
int is_intersected_ls(P a1, P a2, P b1, P b2) {
    // 線分が平行な場合は重なっていないことにする
    if(abs(cross(a2-a1,b2-b1)) < EPS){
        return 0;
    }
    return ( cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < EPS ) &&
        ( cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) < EPS );
}
// aとbの矩形が接しているかどうか(どちらかがどちからを含んでいるものもふくむ
bool isTouchRectangle(Rec &a,Rec &b){
	// aの各頂点がbの中に存在しているかチェック
	for(int i=0;i<4;i++)if(isInPolygon(b.p,a.p[i]))return true;
	// 逆
	for(int i=0;i<4;i++)if(isInPolygon(a.p,b.p[i]))return true;
	// 各辺が他方のどれかの辺と接しているか
	for(int i=0;i<4;i++){
		int curi=i;
		int prvi=(i-1+4)%4;
		for(int j=0;j<4;j++){
			int curj=j;
			int prvj=(j-1+4)%4;
			if(is_intersected_ls(a.p[curi],a.p[prvi],b.p[curj],b.p[prvj]))return true;
		}
	}
	return false;
}
// a1,a2を端点とする線分とb1,b2を端点とする線分の交点計算
P intersection_ls(P a1, P a2, P b1, P b2) {
  P b = b2-b1;
  double d1 = abs(cross(b, a1-b1));
  double d2 = abs(cross(b, a2-b1));
  double t = d1 / (d1 + d2);

  return a1 + (a2-a1) * t;
}
// a1,a2を通る直線とb1,b2を通る直線の交差判定
int is_intersected_l(P a1, P a2, P b1, P b2) {
  return !EQ( cross(a1-a2, b1-b2), 0.0 );
}
// a1,a2を通る直線とb1,b2を通る直線の交点計算
P intersection_l(P a1, P a2, P b1, P b2) {
  P a = a2 - a1; P b = b2 - b1;
  return a1 + a * cross(b, b1-a1) / cross(b, a);
}
// 単位ベクトルを求める
P normalVector(P p){
	return p/abs(p);
}
// 法線ベクトルを求める
P unitVector(P a){
	return P(-a.imag(),a.real());
}
// 単位法線ベクトルを求める
P unitNormalVector(P tmp){
	P e=P(-tmp.imag(),tmp.real());
	e/=abs(e);
	return e;
}
// 座標の回転(座標pにある点を,半時計回りにa(ラジアン)回転)
P roundPoint(P p,double a){
	return P(cos(a)*p.real()-sin(a)*p.imag(),sin(a)*p.real()+cos(a)*p.imag());
}
/*
円周と線分の交差判定
*/
bool isCircleCrossLine(P a,P b,P c,double r){
	double d1 = abs(a-c);
	double d2 = abs(b-c);
    // 線分が中に含まれるとき、ここのコメントアウトをはずせばtrue(交差)となる
	//if(d1<r&&d2<r)
	//	return true;
	double d = distance_ls_p(a,b,c);
	return (EQ(d,r)||d<r);
}
// 三角形の内部に点があるかどうか
// 外積の正負がすべて同じなら内部に点あり
bool isInTriangle(P p1,P p2,P p3,P s){
	P a=p1-s;
	P b=p2-s;
	P c=p3-s;
	return ((cross(a,b)>0&&cross(b,c)>0&&cross(c,a)>0)||(cross(a,b)<0&&cross(b,c)<0&&cross(c,a)<0));
}
// 矩形の中に点が存在するかどうか
bool isInRectangle(P p1,P p2,P p3,P p4,P s){
	P a=p1-s;
	P b=p2-s;
	P c=p3-s;
    P d=p4-s;
	return ((cross(a,b)>0&&cross(b,c)>0&&cross(c,d)>0&&cross(d,a)>0)
        ||(cross(a,b)<0&&cross(b,c)<0&&cross(c,d)<0&&cross(d,a)<0));
}
// 三角形の面積を座標から計算
double calcAreaOfTriangle(P a,P b,P c){
	return abs((b.real()-a.real())*(c.imag()-a.imag()) - (c.real()-a.real())*(b.imag()-a.imag()))/2;
}
// 与えられた円の範囲内に点が存在するかどうか
bool isContainingDot(P c,double r,P a){
	return (((c.real()-a.real())*(c.real()-a.real())
		+(c.imag()-a.imag())*(c.imag()-a.imag())<r*r)
		||EQ((c.real()-a.real())*(c.real()-a.real())
		+(c.imag()-a.imag())*(c.imag()-a.imag()),r*r));
}
// 多角形の面積公式
double calcPolygonArea(vector<P> p){
	double sum=0;
	for(int i = 0; i < p.size(); i++)
		sum+=cross(p[i],p[(i+1)%(p.size())]);
	return abs(sum/2);
}
// 2ベクトル間の角度
// aからbへ左周りで何度か(0->2*PI)
double diffAngle(P a,P b){
    double angle=atan2(cross(a,b),dot(a,b));
    if(angle<0)
        return 2*PI+angle;
    return angle;
}
// 2つのベクトルの重なっている部分の長さを返す
// もし重なっていなければ0を返す
double multipleLength(P a,P b,P c,P d){
    Edge e1=make_pair(a,b);
    Edge e2=make_pair(c,d);
    // 平行であるかどうか
    if(!(is_parallel(e1.first,e2.first,e1.second,e2.second)
        &&is_parallel(e1.first,e1.second,e2.first,e2.second)))
        return 0;
    double dist=0;
    // 両方乗っている
    if(EQ(distance_ls_p(e1.first,e1.second,e2.first),0)&&EQ(distance_ls_p(e1.first,e1.second,e2.second),0))
        dist=abs(e2.first-e2.second);
    else if(EQ(distance_ls_p(e2.first,e2.second,e1.first),0)&&EQ(distance_ls_p(e2.first,e2.second,e1.second),0))
        dist=abs(e1.first-e1.second);
    else if(EQ(distance_ls_p(e1.first,e1.second,e2.first),0)){
        // どちらが線上にあるか
        if(EQ(distance_ls_p(e2.first,e2.second,e1.first),0))
            dist=abs(e1.first-e2.first);
        else
            dist=abs(e1.second-e2.first);
    }
    else if(EQ(distance_ls_p(e1.first,e1.second,e2.second),0)){
        if(EQ(distance_ls_p(e2.first,e2.second,e1.first),0))
            dist=abs(e1.first-e2.second);
        else
            dist=abs(e1.second-e2.second);
    }
    return dist;
}
// 2点を通る半径rの円の中点を求める
pair<P,P> calcCircleCenterPoint(P dot1,P dot2,double r){
    double v=abs(dot1-dot2);
    double x = sqrt(r*r - (v/2)*(v/2));
    // 二組の単位法線ベクトル
    P hose[2];
    double x1=-(dot1.imag()-dot2.imag());
    double y1=(dot1.real() - dot2.real());
    hose[0]=P(x1,y1);
    double y2=-y1;
    double x2=-x1;
    hose[1]=P(x2,y2);
    double dd1=abs(hose[0]);
    double dd2=abs(hose[1]);
    hose[0]/=dd1;hose[0]*=x;
    hose[1]/=dd2;hose[1]*=x;
    P tmp=(dot1+dot2);
    tmp/=2;
    hose[0]+=tmp;
    hose[1]+=tmp;
    return make_pair(hose[0],hose[1]);
}
// 4線分が端点以外でクロスしているかどうかを判定
bool checkCross(const vector<Edge> &vec){
    for(int i=0;i<vec.size();i++){
        for(int j=i+1;j<vec.size();j++){
            // 線分がクロスしているかどうか
            if(is_intersected_ls(vec[i].first,vec[i].second,vec[j].first,vec[j].second)){
                // している場合、端点以外でクロスしているなら、false
                P p=intersection_ls(vec[i].first,vec[i].second,vec[j].first,vec[j].second);
                if(!(EQ(p,vec[i].first)||EQ(p,vec[i].second)))
                    return false;
            }
        }
    }
    return true;
}
// 引き数で与えられた4つの点が矩形を作るどうかを判定
bool checkRec(const vector<P> &squ){
    vector<int> v;
    for(int i=0;i<squ.size();i++)v.push_back(i);
    do{
        vector<Edge> ve;
        for(int i=0;i<4;i++)
            ve.push_back(make_pair(squ[v[i]],squ[v[(i+1)%4]]));
        // ここですべての線分がクロスするかどうかを計算
        if(checkCross(ve)){
            // 線分の長さを確認
            if(EQ(abs(ve[0].first-ve[0].second),abs(ve[2].first-ve[2].second)))
                if(EQ(abs(ve[1].first-ve[1].second),abs(ve[3].first-ve[3].second)))
                    // 直行
                    if(is_orthogonal(ve[0].first,ve[0].second,ve[1].first,ve[1].second))
                        if(is_orthogonal(ve[2].first,ve[2].second,ve[3].first,ve[3].second))
                        return true;
        }
    }while(next_permutation(v.begin(),v.end()));
    return false;
}
// 引き数で与えられた4つの点が正方形を作るかどうかを判定
bool checkSqu(const vector<P> &squ){
    vector<int> v;
    for(int i=0;i<squ.size();i++)v.push_back(i);
    do{
        vector<Edge> ve;
        for(int i=0;i<4;i++)
            ve.push_back(make_pair(squ[v[i]],squ[v[(i+1)%4]]));
        // ここですべての線分がクロスするかどうかを計算
        if(checkCross(ve)){
            // 線分の長さを確認
            double d=abs(ve[0].first-ve[0].second);
            for(int i=1;i<4;i++){
                double d2=abs(ve[i].first-ve[i].second);
                if(!EQ(d,d2))return false;
            }
            // 直行確認
            if(is_orthogonal(ve[0].first,ve[0].second,ve[1].first,ve[1].second))
                if(is_orthogonal(ve[2].first,ve[2].second,ve[3].first,ve[3].second))
                    return true;
        }
    }while(next_permutation(v.begin(),v.end()));
    return false;
}
// 二円の共通接線を構成する4直線を求める(二円はお互い接したりどちらかをふくんだりしない)
vector<pair<P,P> > calcCommonTangentialLine(P p1,double r1,P p2,double r2){
	vector<pair<P,P> > res;
	if(r1>r2){
		swap(r1,r2);
		swap(p1,p2);
	}
	// 共通外接線
	{
		double d=abs(p1-p2);
		double a=abs(r1-r2);
		double b=sqrt(d*d-a*a);
		double sita=acos(b/d);
		P e=normalVector(roundPoint((roundPoint((p2-p1),sita)),PI/2));
		res.push_back(make_pair(e*r1+p1,e*r2+p2));
		P e2=normalVector(roundPoint((roundPoint((p2-p1),-sita)),-PI/2));
		res.push_back(make_pair(e2*r1+p1,e2*r2+p2));
	}
	// 共通内接線
	{
		P cp=(r1*p1+r2*p2)/(r1+r2);
		double u=abs(cp-p1);
		double sita=acos(r1/u);
		P e=normalVector(roundPoint(cp-p1,sita));
		res.push_back(make_pair(e*r1+p1,-e*r2+p2));
		P e2=normalVector(roundPoint(cp-p1,-sita));
		res.push_back(make_pair(e2*r1+p1,-e2*r2+p2));
	}
	return res;
}
/*
  与えられた3点a,b,c,をa->b->cと進むとき
  a->bで時計方向に折れて,b->c
  a->bで半時計方向に折れて,b->c
  a->bで逆を向いてaを通り越してb->c
  a->bでそのままb->c
  a->bで逆を向いてb->c
  のどれであるかを判定
*/
int ccw(P a,P b, P c){
  b-=a;c-=a;
  if(cross(b,c)>0&&!EQ(cross(b,c),0))return 1;// counter clockwise
  if(cross(b,c)<0&&!EQ(cross(b,c),0))return -1;// clockwise
  if(dot(b,c)<0&&!EQ(dot(b,c),0))return 2; // c-a-b on line
  if(!EQ(abs(b),abs(c))&&abs(b)<abs(c))return -2; // a-b-c on line
  return 0;
}
// 凸多角形の切断を行う
// lineのfirst側から見て右の多角形が返る
// 多角形は上が+y,右が+xの座標系で座標を時計周りに格納したvectorで表す
// lineは基本的にmakeDivisorで作成
vector<P> convex_cut(vector<P> polygon,pair<P,P> line){
  vector<P> resPolygon;
  int n=polygon.size();
  for(int i=0;i<n;i++){
    P A=polygon[i];
    P B=polygon[(i+1)%n];
    if(ccw(line.first,line.second,A)!=-1)
      resPolygon.push_back(A);
    if(ccw(line.first,line.second,A)*ccw(line.first,line.second,B)<0)
      resPolygon.push_back(intersection_l(A,B,line.first,line.second));
  }
  return resPolygon;
}
class Point{
public:
  double x,y;
  bool operator<(const Point &p)const{
    if(EQ(p.x,x)){
      if(EQ(p.y,y))return false;
      return y<p.y;
    }
    return x<p.x;
  }
  Point(double _x,double _y){
    x=_x;
    y=_y;
  }
  Point(){}
};

int n;
set<Point> points;
vector<P> initPoint;
typedef pair<int,int> pii;
//double d[2501][2501];
map<pii,double> d;
struct edge{
  int to;
  double cost;
};
int V;
vector<edge> G[10010];
vector<P> nodes;
const int INF=1000000000;

struct Sit{
  int p1,p2;
  double cost;
  bool operator<(const Sit& s)const{
    return cost>s.cost;
  }
  Sit(){}
  Sit(int _p1,int _p2,double _cost){
    p1=_p1;
    p2=_p2;
    cost=_cost;
  }
};

double dijkstra(int s1,int s2){
  // for(int i=0;i<2501;i++)
  //   for(int j=0;j<2501;j++)
  //     d[i][j]=INF;
  d.clear();
  d[pii(s1,s2)]=0;
  //d[s1][s2]=0;
  priority_queue<Sit> pq;
  pq.push(Sit(s1,s2,0));
  while(pq.size()){
    Sit p=pq.top();pq.pop();
    if(p.p1==p.p2){
      // cout<<p.p1<<" "<<p.p2<<endl;
      // cout<<p.cost<<endl;
    }
    // コストがすでに最適値を越えている
    if(d.count(pii(p.p1,p.p2))>0&&
       !EQ(d[pii(p.p1,p.p2)],p.cost)&&d[pii(p.p1,p.p2)]<p.cost)
      continue;
    for(int i=0;i<G[p.p1].size();i++){
      int nxtp1=G[p.p1][i].to;
      double ncost1=G[p.p1][i].cost;
      for(int j=0;j<G[p.p2].size();j++){
	int nxtp2=G[p.p2][j].to;
	// y座標が同じ箇所へ移動する
	if(!EQ(nodes[nxtp1].imag(),nodes[nxtp2].imag()))
	  continue;
	double ncost2=G[p.p2][j].cost;
	const double ncost=ncost1+ncost2+p.cost;
	if(d.count(pii(nxtp1,nxtp2))==0
	   ||(!EQ(d[pii(nxtp1,nxtp2)],ncost)
	      &&d[pii(nxtp1,nxtp2)]>ncost)){
	  d[pii(nxtp1,nxtp2)]=ncost;
	  pq.push(Sit(nxtp1,nxtp2,ncost));
	}
      }
    }
    for(int i=0;i<G[p.p1].size();i++){
      int nxtp1=G[p.p1][i].to;
      double ncost1=G[p.p1][i].cost;
      // y座標が同じ箇所へ移動する
      if(!EQ(nodes[nxtp1].imag(),nodes[p.p2].imag()))
	continue;
      double ncost2=0;
      int nxtp2=p.p2;
      const double ncost=ncost1+ncost2+p.cost;
      if(d.count(pii(nxtp1,nxtp2))==0
	 ||(!EQ(d[pii(nxtp1,nxtp2)],ncost)
	    &&d[pii(nxtp1,nxtp2)]>ncost)){
      // if(!EQ(d[pii(nxtp1,nxtp2)],ncost)
      // 	 &&d[pii(nxtp1,nxtp2)]>ncost){
	d[pii(nxtp1,nxtp2)]=ncost;
	pq.push(Sit(nxtp1,nxtp2,ncost));
      }
    }
    for(int i=0;i<G[p.p2].size();i++){
      int nxtp2=G[p.p2][i].to;
      double ncost2=G[p.p2][i].cost;
      // y座標が同じ箇所へ移動する
      if(!EQ(nodes[p.p1].imag(),nodes[nxtp2].imag()))
	continue;
      double ncost1=0;
      int nxtp1=p.p1;
      const double ncost=ncost1+ncost2+p.cost;
      if(d.count(pii(nxtp1,nxtp2))==0
	 ||(!EQ(d[pii(nxtp1,nxtp2)],ncost)
	    &&d[pii(nxtp1,nxtp2)]>ncost)){
	// if(!EQ(d[pii(nxtp1,nxtp2)],ncost)
	// 	 &&d[pii(nxtp1,nxtp2)]>ncost){
	d[pii(nxtp1,nxtp2)]=ncost;
	pq.push(Sit(nxtp1,nxtp2,ncost));
      }
    }
    
  }
  double res=INF;
  for(int i=0;i<V;i++){
    if(d.count(pii(i,i))>0)
      res=min(res,d[pii(i,i)]);
  }
  return res;
}

int main(){
  while(cin>>n&&n){
    nodes.clear();
    for(int i=0;i<10010;i++)G[i].clear();
    points.clear();
    initPoint.clear();
    for(int i=0;i<n;i++){
      int x,y;
      cin>>x>>y;
      initPoint.push_back(P(x,y));
      points.insert(Point(x,y));
    }
    // y=initPoint[i].imag()と各線分の交点を求める
    for(int i=0;i<n;i++){
      for(int j=1;j<n;j++){
	if(is_intersected_ls(P(-2000,initPoint[i].imag()),
			     P(2000,initPoint[i].imag()),
			     initPoint[j],initPoint[j-1])){
	  P cp=intersection_ls(P(-2000,initPoint[i].imag()),
			  P(2000,initPoint[i].imag()),
			  initPoint[j],initPoint[j-1]);
	  points.insert(Point(cp.real(),cp.imag()));
	}
      }
    }
    set<Point>::iterator it=points.begin();
    set<Point>::iterator iit=points.begin();iit++;
    V=points.size();
    //cout<<V<<endl;
    int idx=1;
    for(;iit!=points.end();it++,iit++){
      edge e;
      e.cost=abs(P(it->x,it->y)-P(iit->x,iit->y));
      e.to=idx;
      G[idx-1].push_back(e);
      e.to=idx-1;
      G[idx].push_back(e);
      idx++;
      //cout<<e.cost<<endl;
    }
    int s1,s2;
    it=points.begin();
    int cnt=0;
    for(;it!=points.end();it++){
      if(EQV(P(it->x,it->y),initPoint[0]))s1=cnt;
      else if(EQV(P(it->x,it->y),initPoint[n-1]))s2=cnt;
      cnt++;
      nodes.push_back(P(it->x,it->y));
    }
    // for(int i=0;i<nodes.size();i++)
    //   cout<<nodes[i]<<endl;
    double res=dijkstra(s1,s2);
    printf("%.10f\n",res);
  }

  return 0;
}