Problem: You are playing a game and your goal is to maximize your expected gain. At the beginning of the game, a pawn is put, uniformly at random, at a position p\in\\{1,2,\dots, N\\}. The N positions are arranged on a circle (so that 1 is between N and 2).

The game consists of turns. At each turn you can either end the game, and get A_p dollars (where p is the current position of the pawn), or pay B_p dollar to keep playing. If you decide to keep playing, the pawn is randomly moved to one of the two adjacent positions p-1, p+1 (with the identifications 0 = N and N+1=1).

What is the expected gain of an optimal strategy?

Note: The "expected gain of an optimal strategy" shall be defined as the supremum of the expected gain among all strategies such that the game ends in a finite number of turns.

Constraints

* 2 \le N \le 200,000
* 0 \le A_p \le 10^{12} for any p = 1,\ldots, N
* 0 \le B_p \le 100 for any p = 1, \ldots, N
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N


Output

Print a single real number, the expected gain of an optimal strategy. Your answer will be considered correct if its relative or absolute error does not exceed 10^{-10}.

Examples

Input

5
4 2 6 3 5
1 1 1 1 1


Output

4.700000000000


Input

4
100 0 100 0
0 100 0 100


Output

50.000000000000


Input

14
4839 5400 6231 5800 6001 5200 6350 7133 7986 8012 7537 7013 6477 5912
34 54 61 32 52 61 21 43 65 12 45 21 1 4


Output

7047.142857142857


Input

10
470606482521 533212137322 116718867454 746976621474 457112271419 815899162072 641324977314 88281100571 9231169966 455007126951
26 83 30 59 100 88 84 91 54 61


Output

815899161079.400024414062

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ";
	dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif

using uint=unsigned;
using ull=unsigned long long;

template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
	return os<<vc<t>(all(a));
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"{";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<"}";
}

template<class t>
void print(t x,int suc=1){
	cout<<x;
	if(suc==1)
		cout<<"\n";
	if(suc==2)
		cout<<" ";
}

ll read(){
	ll i;
	cin>>i;
	return i;
}

vi readvi(int n,int off=0){
	vi v(n);
	rep(i,n)v[i]=read()+off;
	return v;
}

template<class T>
void print(const vector<T>&v,int suc=1){
	rep(i,v.size())
		print(v[i],i==int(v.size())-1?suc:2);
}

string readString(){
	string s;
	cin>>s;
	return s;
}

template<class T>
T sq(const T& t){
	return t*t;
}

//#define CAPITAL
void yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<"\n";
	#else
	cout<<"Yes"<<"\n";
	#endif
	if(ex)exit(0);
}
void no(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<"\n";
	#else
	cout<<"No"<<"\n";
	#endif
	if(ex)exit(0);
}
void possible(bool ex=true){
	#ifdef CAPITAL
	cout<<"POSSIBLE"<<"\n";
	#else
	cout<<"Possible"<<"\n";
	#endif
	if(ex)exit(0);
}
void impossible(bool ex=true){
	#ifdef CAPITAL
	cout<<"IMPOSSIBLE"<<"\n";
	#else
	cout<<"Impossible"<<"\n";
	#endif
	if(ex)exit(0);
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int topbit(signed t){
	return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
	return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
	return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
	return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
	return __builtin_popcount(t);
}
int popcount(ll t){
	return __builtin_popcountll(t);
}
bool ispow2(int i){
	return i&&(i&-i)==i;
}
ll mask(int i){
	return (ll(1)<<i)-1;
}

bool inc(int a,int b,int c){
	return a<=b&&b<=c;
}

template<class t> void mkuni(vc<t>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

ll rand_int(ll l, ll r) { //[l, r]
	#ifdef LOCAL
	static mt19937_64 gen;
	#else
	static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
	#endif
	return uniform_int_distribution<ll>(l, r)(gen);
}

template<class t>
void myshuffle(vc<t>&a){
	rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
}

template<class t>
int lwb(const vc<t>&v,const t&a){
	return lower_bound(all(v),a)-v.bg;
}

//VERIFY: yosupo
template<class N>
struct segtree{
	vc<N> buf;
	int s;
	template<class t>
	segtree(vc<t> a){
		int n=a.size();
		s=1;
		while(s<n){s*=2;}
		buf.resize(s*2);
		rep(i,n)
			buf[s+i]=N(a[i]);
		gnr(i,1,s)
			buf[i]=N::merge(buf[i*2],buf[i*2+1]);
	}
	void set(int i,const N&t){
		i+=s;
		buf[i]=t;
		while(i>>=1)buf[i]=N::merge(buf[i*2],buf[i*2+1]);
	}
	N query(int b,int e,int l,int r,int i){
		if(e<=l||r<=b)return N();
		if(b<=l&&r<=e)return buf[i];
		return N::merge(query(b,e,l,(l+r)/2,i*2),query(b,e,(l+r)/2,r,i*2+1));
	}
	N query(int b,int e){
		return query(b,e,0,s,1);
	}
	N getall(){
		return buf[1];
	}
};

//simple range max
struct N{
	int w[4][4];
	N(int v=-1){
		zero(w);
		if(v>=-1)rep(i,4)w[i][i]=1;
		if(v>=0){
			//w[0][0]=1;
			w[0][1]=1;
			w[0][2]=v;
			w[0][3]=v;
			//w[1][1]=1;
			w[1][2]=v;
			w[1][3]=v;
			//w[2][2]=1;
			w[2][3]=1;
			//w[3][3]=1;
		}
	}
	void push(N&,N&){
	}
	static N merge(N x,N y){
		N res(-2);
		rep(i,4)rng(j,i,4)rng(k,i,j+1)res.w[i][j]+=x.w[i][k]*y.w[k][j];
		return res;
	}
};

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	int n;cin>>n;
	vi a=readvi(n);
	vi b=readvi(n);
	
	{
		int i=max_element(all(a))-a.bg;
		rotate(a.bg,a.bg+i,a.ed);
		rotate(b.bg,b.bg+i,b.ed);
	}
	a.pb(a[0]);
	b.pb(b[0]);
	n++;
	
	//dmp(a);
	//dmp(b);
	
	segtree<N> seg(b);
	
	auto val=[&](int i,int j){
		if(i+1==j){
			return (a[i]+a[j])*(j-i);
		}
		N z=seg.query(i+1,j);
		dmp2(j-i-1,z.w[0][3]);
		return (a[i]+a[j])*(j-i)-z.w[0][3]*2;
	};
	
	int ans=0;
	
	set<int> s;
	rep(i,n)s.insert(i);
	rep(i,n-1)ans+=val(i,i+1);
	
	vi cur(n);
	priority_queue<pi> pq;
	auto upd=[&](int i){
		if(i==0||i==n-1)return;
		auto itr=s.find(i);
		assert(itr!=s.ed);
		assert(itr!=s.bg);
		assert(next(itr)!=s.ed);
		int x=*prev(itr),y=*next(itr);
		cur[i]=val(x,y)-val(x,i)-val(i,y);
		pq.emplace(cur[i],i);
	};
	
	rng(i,1,n-1)upd(i);
	
	while(si(pq)){
		int v,i;tie(v,i)=pq.top();pq.pop();
		if(cur[i]!=v)continue;
		if(cur[i]<0)break;
		ans+=cur[i];
		cur[i]=-inf;
		auto itr=s.find(i);
		assert(itr!=s.ed);
		int x=*prev(itr),y=*next(itr);
		s.erase(itr);
		upd(x);
		upd(y);
	}
	
	cout<<((long double)(ans))/(n-1)/2<<endl;
}