Problem: The New Vasjuki village is stretched along the motorway and that's why every house on it is characterized by its shift relative to some fixed point — the xi coordinate. The village consists of n houses, the i-th house is located in the point with coordinates of xi.

TELE3, a cellular communication provider planned to locate three base stations so as to provide every house in the village with cellular communication. The base station having power d located in the point t provides with communication all the houses on the segment [t - d, t + d] (including boundaries).

To simplify the integration (and simply not to mix anything up) all the three stations are planned to possess the equal power of d. Which minimal value of d is enough to provide all the houses in the village with cellular communication.

Input

The first line contains an integer n (1 ≤ n ≤ 2·105) which represents the number of houses in the village. The second line contains the coordinates of houses — the sequence x1, x2, ..., xn of integer numbers (1 ≤ xi ≤ 109). It is possible that two or more houses are located on one point. The coordinates are given in a arbitrary order.

Output

Print the required minimal power d. In the second line print three numbers — the possible coordinates of the base stations' location. Print the coordinates with 6 digits after the decimal point. The positions of the stations can be any from 0 to 2·109 inclusively. It is accepted for the base stations to have matching coordinates. If there are many solutions, print any of them.

Examples

Input

4
1 2 3 4


Output

0.500000
1.500000 2.500000 3.500000


Input

3
10 20 30


Output

0
10.000000 20.000000 30.000000


Input

5
10003 10004 10001 10002 1


Output

0.500000
1.000000 10001.500000 10003.500000

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
import java.math.*;
import java.lang.*;
import java.text.*;

public class threebase {
        public static void main(String[] args) throws Exception {
                Scanner sc = new Scanner(System.in);
                int size = sc.nextInt();
                int[] lis = new int[size];
                for (int w = 0; w < size; w++) {
                        lis[w] = sc.nextInt();
                }
                Arrays.sort(lis);
                double dis = Double.MAX_VALUE;
                ArrayList<Double> locs = new ArrayList<Double>();
                double lower = 0;
                double higher = 1e9;
                double mid=(lower+higher/2);
                while(true)
                {
                        double dis1=lis[0]+mid*2;
                        double dis2=lis[size-1]-mid*2;
                        double dis3=-1;
                        int x=0;
                        for( x=0;x<size;x++)
                        {
                                if(lis[x]>dis1)
                                {
                                        dis3=lis[x];
                                        break;
                                }
                        }
                        if(x==size)x--;
                        for(int y=size-1;y>=0;y--)
                        {
                                if(lis[y]<dis2)
                                {
                                        dis3=lis[y]-dis3;
                                        break;
                                }
                        }
                        if(dis2<dis1)higher=mid;
                        else if(dis3<mid*2)
                        {
                                higher=mid;
                        }
                        else lower=mid;
                        
                        double nmid=(lower+higher)/2;
                        if(Math.abs(nmid-mid)<1e-9)
                        {
                                dis=mid;
                                double range=0;
                       
                                for(int z=0;z<size;z++)
                                {
                                	if(lis[z]>range)
                                	{
                                		locs.add(lis[z]+mid);
                                		range=lis[z]+mid+mid;
                                		range=Math.round(range);
                                	}
                                }
                                while(locs.size()<3)locs.add(range);
                                break;
                        }
                        mid=nmid;
                }
              //  System.out.println(Arrays.toString(lis));
                System.out.printf("%.6f\n", dis);
                System.out.printf("%.6f %.6f %.6f\n", locs.get(0), locs.get(1), locs
                                .get(2));
        }
}