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 <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <iterator>
#include <array>
#include <memory>
#include <random>
//cin.sync_with_stdio(false);
//streambuf
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using ti3 = tuple<int, int, int>;
using vti3 = vector<ti3>;
template<class T, int s>using va = vector<array<T, s>>;
template<class T, class T2> using umap = unordered_map<T, T2>;
template<class T> using uset = unordered_set<T>;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define ALL(a) a.begin(),a.end()
#define rep(i,a) for(int i=0;i<a;i++)
#define rep1(i,a) for(int i=1;i<=a;i++)
#define rrep(i,a) for(int i=(a)-1;i>=0;i--)
#define rrep1(i,a) for(int i=a;i;i--)
#define repi(i,a,b) for(int i=a;i<b;i++);
const ll mod = 1000000007;
template<class T>using heap = priority_queue<T, vector<T>, greater<T>>;
template<class T>using pque = priority_queue<T, vector<T>, function<T(T, T)>>;
template <class T>
inline void hash_combine(size_t & seed, const T & v) {
	hash<T> hasher;
	seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
namespace std {
	template<typename S, typename T> struct hash<pair<S, T>> {
		inline size_t operator()(const pair<S, T> & v) const {
			size_t seed = 0;
			hash_combine(seed, v.first);
			hash_combine(seed, v.second);
			return seed;
		}
	};
	// Recursive template code derived from Matthieu M.
	template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
	struct HashValueImpl {
		static void apply(size_t& seed, Tuple const& tuple) {
			HashValueImpl<Tuple, Index - 1>::apply(seed, tuple);
			hash_combine(seed, std::get<Index>(tuple));
		}
	};
	template <class Tuple>
	struct HashValueImpl<Tuple, 0> {
		static void apply(size_t& seed, Tuple const& tuple) {
			hash_combine(seed, std::get<0>(tuple));
		}
	};
	template <typename ... TT>
	struct hash<std::tuple<TT...>> {
		size_t operator()(std::tuple<TT...> const& tt) const {
			size_t seed = 0;
			HashValueImpl<std::tuple<TT...> >::apply(seed, tt);
			return seed;
		}
	};
}
template<class T>int id(vector<T> &a, T b) {
	return lower_bound(ALL(a), b) - a.begin();
}
ll pow(ll base, ll i, ll mod) {
	ll a = 1;
	while (i) {
		if (i & 1) {
			a *= base;
			a %= mod;
		}
		base *= base;
		base %= mod;
		i /= 2;
	}
	return a;
}
ll gcd(ll a, ll b) {
	while (b) {
		ll c = a%b;
		a = b;
		b = c;
	}
	return a;
}
ll lcm(ll a, ll b) {
	return a / gcd(a, b)*b;
}
int popcnt(unsigned long long a) {
	a = (a & 0x5555555555555555) + (a >> 1 & 0x5555555555555555);
	a = (a & 0x3333333333333333) + (a >> 2 & 0x3333333333333333);
	a = (a & 0x0f0f0f0f0f0f0f0f) + (a >> 4 & 0x0f0f0f0f0f0f0f0f);
	a = (a & 0x00ff00ff00ff00ff) + (a >> 8 & 0x00ff00ff00ff00ff);
	a = (a & 0x0000ffff0000ffff) + (a >> 16 & 0x0000ffff0000ffff);
	return (a & 0xffffffff) + (a >> 32);
}
class unionfind {
	vector<int> par, rank, size_;//????????§??????????????¢???????????????????????????rank???????????????size?????????
public:
	unionfind(int n) :par(n), rank(n), size_(n, 1) {
		iota(ALL(par), 0);
	}
	int find(int x) {
		if (par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y)return;
		if (rank[x] < rank[y])swap(x, y);
		par[y] = x;
		size_[x] += size_[y];
		if (rank[x] == rank[y])rank[x]++;
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	int size(int x) {
		return size_[find(x)];
	}
};
template<class T, class Func = function<T(T, T)>>
class segtree {
	vector<T> obj;
	int offset;
	Func updater;
	T e;
	int bufsize(int num) {
		int i = 1;
		for (; num >i; i <<= 1);
		offset = i - 1;
		return (i << 1) - 1;
	}
	T query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l)return e;
		if (a <= l && r <= b)return obj[k];
		else return updater(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
	}
	/*
	template<class QF = function<T(T, T)>>
	auto query(int a, int b, int k, int l, int r,QF qf) {
	if (r <= a || b <= l)return e;
	if (a <= l && r <= b)return obj[k];
	else return qf(query(a, b, k * 2 + 1, l, (l + r) / 2, qf), query(a, b, k * 2 + 2, (l + r) / 2, r, qf));
	}*/
public:
	T query(int a, int b) {//[a,b)
		return query(a, b, 0, 0, offset + 1);
	}/*
	 template<class QF = function<T(T, T)>>
	 auto query(int a, int b,QF &&qf) {//[a,b)
	 return query(a, b, 0, 0, offset + 1,qf);
	 }*/
	void updateall(int l = 0, int r = -1) {
		if (r < 0)r = offset + 1;
		l += offset, r += offset;
		do {
			l = l - 1 >> 1, r = r - 1 >> 1;
			for (int i = l; i < r; i++)obj[i] = updater(obj[i * 2 + 1], obj[i * 2 + 2]);
		} while (l);
	}
	void update(int k, T &a) {
		k += offset;
		obj[k] = a;
		while (k) {
			k = k - 1 >> 1;
			obj[k] = updater(obj[k * 2 + 1], obj[k * 2 + 2]);
		}
	}
	segtree(int n, T e, const Func &updater = Func()) :obj(bufsize(n), e), e(e), updater(updater) {}
	segtree(vector<T> &vec, T e, const Func &updater = Func()) :obj(bufsize(vec.size()), e), e(e), updater(updater) {
		copy(vec.begin(), vec.end(), obj.begin() + offset);
		updateall();
	}
	typename vector<T>::reference operator[](int n) {
		return obj[n + offset];
	}
};
template<class T = int>
class BIT {//????¬????BIT????????????????????????????????°??????????????????
	vector<T> bit;
	int n;
public:
	BIT(int n) :bit(n + 1, 0) {}
	void add(int i, T x) {
		i++;
		while (i <= n) {
			bit[i] += x;
			i += i&-i;
		}
	}
	T sum(int i) {
		T s = 0;
		i++;
		while (i) {
			s += bit[i];
			i &= i - 1;
		}
		return s;
	}
};
template<class T = int>
class rangeadd {
	BIT<T> b0, b1;
public:
	rangeadd(int n) :b0(n), b1(n) {};
	void add(int l, int r, T x) {//[l,r)
		b0.add(l, -x*(l - 1));
		b1.add(l, x);
		b0.add(r, x*r);
		b1.add(r, -x);
	}
	T sum(int i) {
		if (i < 0)return 0;
		return b0.sum(i) + b1.sum(i)*i;
	}
	T sum(int l, int r) {
		return sum(r - 1) - sum(l - 1);
	}
};
//end of lib
//template<class S=void,int ptr_num, class T = char>class trie {
//	umap<T, trie<S, ptr_num, T> next;
//public:
//	S key;
//	trie<S, ptr_num, T>* ptr[ptr_num] = {};
//	trie(S &&data) :key(data) {}
//	trie(const S &data) :key(data) {}
//	void add(T x,S data) {
//		if (!next.find(x))next.insert(x, data);
//	}
//	trie& operator[](T x) {
//		return next[x];
//	}
//	bool find(T x) {
//		retun next.find(x);
//	}
//};
//template<class T=char>class AhoCorasick {
//	trie<pair<bool,int>, 2, T> tree;
//	AhoCorasick(vector<string> p) {
//		int num = 0;
//		vector<decltype(&tree)> que(p.size(),&tree);
//		for (int i = 0;; i++) {
//			bool end = 1;
//			int i = 0;
//			for (auto a : p) {
//				if (i >= a.size())break;
//				end = ;0
//				que[i] = (*que[i])[a[i]];
//				i++;
//			}
//			if (end)break;
//		}
//	}
//};
int main() {
	int n;
	while (cin >> n, n) {
		vpii x(n);
		rep(i, n)cin >> x[i].first >> x[i].second;
		set<array<int, 5>> dp;
		heap<pair<double, array<int, 5>>> q;
		q.push({ 0,{0,0,n - 2,0,1} });
		for (;;) {
			auto a = q.top(); q.pop();
			if (a.second[1] == a.second[2]) {
				cout << setprecision(10) << (x[a.second[2]].second == x[a.second[2] + 1].second&&a.second[3] != a.second[4] ? x[a.second[2] + 1].first - x[a.second[2]].first : 0) + a.first << endl;
				break;
			}
			if (dp.count(a.second))continue;
			dp.insert(a.second);
			vi l = { max(min(x[a.second[1]].second, x[a.second[1] + 1].second), min(x[a.second[2]].second, x[a.second[2] + 1].second)),min(max(x[a.second[1]].second, x[a.second[1] + 1].second), max(x[a.second[2]].second, x[a.second[2] + 1].second)) };
			l.erase(unique(ALL(l)), l.end());
			for (auto z : l) {
				if (a.second[1] != 0 && x[a.second[1]].second == z)q.push({ a.first + ((x[a.second[1] + 1].second == x[a.second[1]].second ? (a.second[3] ? x[a.second[1] + 1].first - x[a.second[1]].first : 0) : hypot(1,double(x[a.second[1] + 1].first - x[a.second[1]].first) / (x[a.second[1] + 1].second - x[a.second[1]].second))*abs(z - a.second[0])) + (x[a.second[2] + 1].second == x[a.second[2]].second ? 0 : hypot(1,double(x[a.second[2] + 1].first - x[a.second[2]].first) / (x[a.second[2] + 1].second - x[a.second[2]].second))*abs(z - a.second[0]))),{ z,a.second[1] - 1,a.second[2],1,a.second[4] } });
				if (a.second[1] != n - 2 && x[a.second[1] + 1].second == z)q.push({ a.first + ((x[a.second[1] + 1].second == x[a.second[1]].second ? (!a.second[3] ? x[a.second[1] + 1].first - x[a.second[1]].first : 0) : hypot(1,double(x[a.second[1] + 1].first - x[a.second[1]].first) / (x[a.second[1] + 1].second - x[a.second[1]].second))*abs(z - a.second[0])) + (x[a.second[2] + 1].second == x[a.second[2]].second ? 0 : hypot(1,double(x[a.second[2] + 1].first - x[a.second[2]].first) / (x[a.second[2] + 1].second - x[a.second[2]].second))*abs(z - a.second[0]))),{ z,a.second[1] + 1,a.second[2],0,a.second[4] } });
				if (a.second[2] != 0 && x[a.second[2]].second == z)q.push({ a.first + ((x[a.second[1] + 1].second == x[a.second[1]].second ? 0 : hypot(1,double(x[a.second[1] + 1].first - x[a.second[1]].first) / (x[a.second[1] + 1].second - x[a.second[1]].second))*abs(z - a.second[0])) + (x[a.second[2] + 1].second == x[a.second[2]].second ? (a.second[4] ? x[a.second[2] + 1].first - x[a.second[2]].first : 0) : hypot(1,double(x[a.second[2] + 1].first - x[a.second[2]].first) / (x[a.second[2] + 1].second - x[a.second[2]].second))*abs(z - a.second[0]))),{ z,a.second[1],a.second[2] - 1,a.second[3],1 } });
				if (a.second[2] != n - 2 && x[a.second[2] + 1].second == z)q.push({ a.first + ((x[a.second[1] + 1].second == x[a.second[1]].second ? 0 : hypot(1,double(x[a.second[1] + 1].first - x[a.second[1]].first) / (x[a.second[1] + 1].second - x[a.second[1]].second))*abs(z - a.second[0])) + (x[a.second[2] + 1].second == x[a.second[2]].second ? (!a.second[4] ? x[a.second[2] + 1].first - x[a.second[2]].first : 0) : hypot(1,double(x[a.second[2] + 1].first - x[a.second[2]].first) / (x[a.second[2] + 1].second - x[a.second[2]].second))*abs(z - a.second[0]))),{ z,a.second[1],a.second[2] + 1 ,a.second[3],0} });
			}
		}
	}
}