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 static java.lang.Math.*;
import java.math.*;

public class Main implements Runnable {
	BufferedReader in;
	PrintStream out;  
	StringTokenizer st = new StringTokenizer("");
	static boolean local = false;

	double eps = 1e-7;
	int n;
	double [] x;
	double [] cx = new double [3];
	
	public static void main(String [] args) throws Exception {
		if (args.length > 0) local = true;
		new Thread(new Main()).start();
	}   

	double get(int i, int j) {
		if (j <= i) return x[i];
		return (x[j] + x[i]) / 2;
	}

	boolean good(double m) {
		int cur = 0;
		for (int i = 0; i < 3; i++) {
			int nc = cur;
			while (x[nc] - x[cur] < m) {
				nc++;
				if (nc == n) {
					cx[i] = get(cur, nc - 1);
					return true;
				}
			}
			cx[i] = get(cur, nc - 1);
			cur = nc;
		}	
		return false;
	}


	public void run() {
		try {
			Locale.setDefault(Locale.US);
			in = local ? new BufferedReader(new FileReader("input.txt")) : new BufferedReader(new InputStreamReader(System.in));
			out = local ? new PrintStream(new File("output.txt")) : new PrintStream(System.out);

			n = nextInt();
			x = new double[n];

			for (int i = 0; i < n; i++) {
				x[i] = nextInt();
			} 

			Arrays.sort(x);

			double l = 0, r = 1000000000D;

			for (int iter = 0; iter < 60; iter++) {
				double m = (l + r) / 2;
				if (good(m)) {
					r = m;
				} else {
					l = m;
				}
			}

			good(l + eps);

			out.println((l + eps) / 2);
			for (int i = 0; i < 3; i++)
				out.print(cx[i] + " ");

		}
		catch (Exception e) {
			e.printStackTrace();
		}
	}

	boolean seekForToken() {
 		try {
			while (!st.hasMoreTokens()) {
				String s = in.readLine();
				if (s == null) {
				 	return false;
				}
			 	st = new StringTokenizer(s);
			}
			return true;
		}
		catch (IOException e) {
		 	e.printStackTrace();
		 	return false;
		}
 	}

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

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

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

 	BigInteger nextBigInteger() {
 	 	return new BigInteger(nextToken());
 	}

 	String nextToken() {
 	 	seekForToken();
 	 	return st.nextToken();
 	}

}