Problem: We have 2N pots. The market price of the i-th pot (1 ≤ i ≤ 2N) is p_i yen (the currency of Japan).

Now, you and Lunlun the dachshund will alternately take one pot. You will go first, and we will continue until all the pots are taken by you or Lunlun. Since Lunlun does not know the market prices of the pots, she will always choose a pot randomly from the remaining pots with equal probability. You know this behavior of Lunlun, and the market prices of the pots.

Let the sum of the market prices of the pots you take be S yen. Your objective is to maximize the expected value of S. Find the expected value of S when the optimal strategy is adopted.

Constraints

* 1 ≤ N ≤ 10^5
* 1 ≤ p_i ≤ 2 × 10^5
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N
p_1
:
p_{2N}


Output

Print the expected value of S when the strategy to maximize the expected value of S is adopted. The output is considered correct if its absolute or relative error from the judge's output is at most 10^{-9}.

Examples

Input

1
150000
108


Output

150000.0


Input

2
50000
50000
100000
100000


Output

183333.3333333333

Solution (in CPP):

Solution:
                                                    #include <bits/stdc++.h>
                                                    #include<iostream>
                                                    #include<cstdio>
                                                    #include<vector>
                                                    #include<queue>
                                                    #include<map>
                                                    #include<cstring>
                                                    #include<string>
                                                    #include <math.h>
                                                    #include<algorithm>
                                                //    #include <boost/multiprecision/cpp_int.hpp>
                                                    #include<functional>
                                           #define int long long
                                                    #define inf  10000000000007
                                                    #define pa pair<int,int>
                                                    #define ll long long
                                                    #define pal pair<double,pa>
                                                    #define ppa pair<pa,int>
                                                    #define ppap pair<int,pa>
                                                    #define ssa pair<string,int>
                                                    #define  mp make_pair
                                                    #define  pb push_back
                                                    #define EPS (1e-10)
                                                    #define equals(a,b) (fabs((a)-(b))<EPS)
                                             
                                                    using namespace std;
                                          
                                                    class Point{
                                                    	public:
                                                    	double x,y;
                                                    	Point(double x=0,double y=0):x(x),y(y) {}
                                                    	Point operator + (Point p) {return Point(x+p.x,y+p.y);}
                                                    	Point operator - (Point p) {return Point(x-p.x,y-p.y);}
                                                    	Point operator * (double a) {return Point(x*a,y*a);}
                                                    	Point operator / (double a) {return Point(x/a,y/a);}
                                                    	double absv() {return sqrt(norm());}
                                                    	double norm() {return x*x+y*y;}
                                                    	bool operator < (const Point &p) const{
                                                    		return x != p.x ? x<p.x: y<p.y;
                                                    	}
                                                    	bool operator == (const Point &p) const{
                                                    		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
                                                    	}
                                                    };
                                                    typedef Point Vector;
                                             
                                                    struct Segment{
                                                    Point p1,p2;
                                                    };
                                                     double dot(Vector a,Vector b){
                                                    	return a.x*b.x+a.y*b.y;
                                                    }
                                                    double cross(Vector a,Vector b){
                                                    	return a.x*b.y-a.y*b.x;
                                                    }
                                                
                        bool parareru(Point a,Point b,Point c,Point d){
                        //	if(abs(cross(a-b,d-c))<EPS)cout<<"dd "<<cross(a-b,d-c)<<endl;
                        	return abs(cross(a-b,d-c))<EPS;
                        }
                        double distance_ls_p(Point a, Point b, Point c) {
                          if ( dot(b-a, c-a) < EPS ) return (c-a).absv();
                          if ( dot(a-b, c-b) < EPS ) return (c-b).absv();
                          return abs(cross(b-a, c-a)) / (b-a).absv();
                        }
                        bool is_intersected_ls(Segment a,Segment b) {
                        	if(a.p1==b.p1||a.p2==b.p1||a.p1==b.p2||a.p2==b.p2) return false;
                        	if(parareru((a.p2),(a.p1),(a.p1),(b.p2))&&parareru((a.p2),(a.p1),(a.p1),(b.p1))){
                        //		cout<<"sss"<<endl;
                        		if(dot(a.p1-b.p1,a.p1-b.p2)<EPS) return true;
                        		if(dot(a.p2-b.p1,a.p2-b.p2)<EPS) return true;
                        		if(dot(a.p1-b.p1,a.p2-b.p1)<EPS) return true;
                        		if(dot(a.p1-b.p2,a.p2-b.p2)<EPS) return true;
                        		return false;
                        	}
                          else return ( cross(a.p2-a.p1, b.p1-a.p1) * cross(a.p2-a.p1, b.p2-a.p1) < EPS ) && ( cross(b.p2-b.p1, a.p1-b.p1) * cross(b.p2-b.p1, a.p2-b.p1) < EPS );
                        }
                         
                        double segment_dis(Segment a,Segment b){
                        	if(is_intersected_ls(a,b))return 0;
                        	double r=distance_ls_p(a.p1, a.p2, b.p1);
                        	r=min(r,distance_ls_p(a.p1, a.p2, b.p2));
                        	r=min(r,distance_ls_p(b.p1, b.p2, a.p2));
                        	r=min(r,distance_ls_p(b.p1, b.p2, a.p1));
                        	return r;
                        }
                        Point intersection_ls(Segment a, Segment b) {
                          Point ba = b.p2-b.p1;
                          double d1 = abs(cross(ba, a.p1-b.p1));
                          double d2 = abs(cross(ba, a.p2-b.p1));
                          double t = d1 / (d1 + d2);
                         
                          return a.p1 + (a.p2-a.p1) * t;
                        }
                         
                                        string itos( int i ) {
                                        ostringstream s ;
                                        s << i ;
                                        return s.str() ;
                                        }
                                         
                                        int gcd(int v,int b){
                                        	if(v>b) return gcd(b,v);
                                        	if(v==b) return b;
                                        	if(b%v==0) return v;
                                        	return gcd(v,b%v);
                                        }
                         
                                        double distans(double x1,double y1,double x2,double y2){
                                        	double rr=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
                                        	return sqrt(rr);
                                        	
                                        }
                                        /*
                        int pr[100010];
                        //int inv[100010];
                        */ 
                        int beki(int wa,int rr,int warukazu){
                        	if(rr==0) return 1ll;
                        	if(rr==1) return wa%warukazu;
                        	if(rr%2==1) return (beki(wa,rr-1,warukazu)*wa)%warukazu;
                        	int zx=beki(wa,rr/2,warukazu);
                        	return (zx*zx)%warukazu;
                        }
                          /*
                        void gya(){
                        	pr[0]=1;
                        	for(int i=1;i<100010;i++){
                        		pr[i]=(pr[i-1]*i)%inf;
                        	}
                        	for(int i=0;i<100010;i++) inv[i]=beki(pr[i],inf-2);
                        	
                        }
                         
                        */
                         //sort(ve.begin(),ve.end(),greater<int>());
                                                 //----------------kokomade tenpure------------
                        //vector<double> ans(100000000),ans2(100000000);
                        
                        int par[200100],ranks[200100],kosuu[200100];     
                         
                        void shoki(int n){
                        	for(int i=0;i<n;i++){
                        		par[i]=i;
                        		ranks[i]=0;
                        		kosuu[i]=1;
                        	}
                        }
                         
                        int root(int x){
                        	return par[x]==x ? x : par[x]=root(par[x]);
                        }
                         
                        bool same(int x,int y){
                        return root(x)==root(y);
                        }
                         
                        void unite(int x,int y){
                         x=root(x);
                         y=root(y);
                        	int xx=kosuu[x],yy=kosuu[y];
                         if(x==y) return;
                        	if(ranks[x]<ranks[y]){
                        		par[x]=y;
                        		kosuu[y]=yy+xx;
                        	}
                         else {
                        	par[y]=x;
                        	if(ranks[x]==ranks[y]) ranks[x]=ranks[x]+1;
                         	kosuu[x]=yy+xx;
                         }
                        	return;
                        }
                        
            int N=262144;
            pa sgt[530000];
             
            pa minis(int i,int j ){
            if(i==j) return sgt[i];
            	else if(i%2==1){
            		pa z=minis(i+1,j);
            		if(sgt[i].first>z.first)return sgt[i] ;
            		else return z;
            	}
            		else if(j%2==0) 	{
            		pa z=minis(i,j-1);
            		if(sgt[j].first>z.first)return sgt[j] ;
            		else return z;
            	}
            else return minis(i/2,j/2);
            }
             
            pa sgtmin(int i ,int j) {
            	return minis(i+N,j+N);
            }
             
            void upd(int x,int y){
            	x+=N;
            sgt[x].first=y;
            	sgt[x].second=x;
            x=x/2;
            while(x != 0){
            	if(sgt[2*x+1].first>sgt[2*x].first){
            		sgt[x]=sgt[2*x+1];
            	}
            	else sgt[x]=sgt[2*x];
             
            x=x/2;
            }
            }
              
             
                 int n,p;
            int x[100030],sc[100030]={0};
            int rui[100040]={0};
            int score[100040];
                 vector<int> ve;
                    signed main(){
            int n;
                    	cin>>n;
                    	for(int i=1;i<=2*n;i++){
        int y;
        cin>>y;
        ve.pb(-y);
        }
        sort(ve.begin(),ve.end());
        for(int i=0;i<2*n;i++) ve[i] *=-1;
         
        double ans=0;
            for(int i=0;i<2*n;i++){
        ans+= (ve[i]+0.0)*(2*n-(i+1)+0.0)/(2*n-1.0);
        }
                    	printf("%.10lf\n",ans);
                    	return 0;
                    }