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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class ThreeBaseStations {

    private static void solve(IO io, int n, int[] arr) {
        Arrays.sort(arr);
        double accuracy = 0.0000001;
        double low = 0;
        double high = arr[n - 1] - arr[0];

        int count = 0;
        while (high - low >= accuracy && count <= 200){
            //System.out.println(low +", " + high);
            double mid = low + (high - low) / 2;
            if(check(arr, mid))
                high = mid;
            else low = mid + accuracy;
            ++count;
        }

        //double d = Math.floor(low * (1 / accuracy)) * accuracy;
        double d = Math.round(low * 1000000) / 1000000D ;
        System.out.println(d);
        List<Double> posi = new ArrayList<>();
        //place them again
        double coveredTill = arr[0] - (2 * d) - 1;
        for(int i = 0; i < n; ++i){
            if(arr[i] - coveredTill >= accuracy){
                posi.add(arr[i] + d);
                coveredTill = arr[i] + 2 * d;
            }
        }

        while (posi.size() < 3)
            posi.add(posi.get(posi.size() - 1));


        for(double p : posi)
            System.out.print(p +" ");
        System.out.println();
    }

    private static boolean check(int[] arr, double d) {

        int n = arr.length;
        double coveredTill = arr[0] - (2 * d) - 1;
        int reqdStations = 0;
        for(int i = 0; i < n; ++i){
            if(arr[i] > coveredTill){
                ++reqdStations;
                //System.out.println("place at " + (arr[i] + d));
                //place at d dist from here
                coveredTill = arr[i] + 2 * d;
            }
        }
        return reqdStations <= 3;
    }
    public static void main(String[] args) {
        IO io = new IO();

        int n = io.nextInt();
        int[] arr = io.readArray(n);
        //TODO read inputs
        solve(io, n, arr);
        io.close();
    }
    private static class IO extends PrintWriter {

        private BufferedReader br;
        StringTokenizer st;

        public IO() {
            super(System.out);
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        List<Integer> readList(int n){
            List<Integer> list = new ArrayList<>(n);
            for(int i = 0; i < n; ++i)
                list.add(nextInt());
            return list;
        }
        int[] readArray(int n){
            int[] arr = new int[n];
            for(int i = 0; i < n; ++i)
                arr[i] = nextInt();

            return arr;
        }
        long[] readLongArray(int n){
            long[] arr = new long[n];
            for(int i = 0; i < n; ++i)
                arr[i] = nextLong();

            return arr;
        }

        double[] readDoubleArray(int n){
            double[] arr = new double[n];
            for(int i = 0; i < n; ++i)
                arr[i] = nextDouble();
            return arr;
        }
    }
}