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.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Locale;
import java.util.StringTokenizer;


public class C implements Runnable {

	
	private double[] x;
	double[] posAns = new double[3];
	double EPS = 1e-8;

	void solve_() throws IOException {
		int n = nextInt();
		x = new double[n];
		for (int i = 0; i < n; ++i) {
			x[i] = nextDouble();
		}
		Arrays.sort(x);
		if (n == 1) {
			out.printf("%.7f\n%.7f %.7f %.7f\n", 0., x[0], 0., 0.);
			return;
		}
		int[] d = new int[x.length];
		d[0] = 0;
		for (int i = 1; i < d.length; ++i) {
			int pos = d[i - 1];
			for (; pos < i && (x[pos] - x[0] <= x[i] - x[pos + 1] + EPS); ++pos)
				;
			d[i] = pos - 1;
		}
		double min = Double.POSITIVE_INFINITY;
		
		for (int i = 0; i < x.length - 1; ++i) {
			double val1 = x[x.length - 1] - x[i + 1];
			double val2 = x[d[i]] - x[0];
			double val3 = Math.max(x[i] - x[d[i] + 1], 0);
			double val = Math.max(Math.max(val1, val2), val3);
			if (val < min) {
				min = val;
				posAns[2] = (x[x.length - 1] + x[i + 1]) / 2.;
				posAns[1] = i != d[i] ? (x[d[i] + 1] + x[i]) / 2. : x[i];
				posAns[0] = (x[d[i]] + x[0]) / 2.;
			}
		}
		out.printf("%.7f\n", min / 2.);
		for (double i : posAns) {
			out.printf("%.7f ", i);
		}
		out.println();
	}
	
	private void solve() throws IOException {
		int n = nextInt();
		x = new double[n];
		for (int i = 0; i < n; ++i) {
			x[i] = nextDouble();
		}
		Arrays.sort(x);
		double up = 1e9 / 2.;
		double down = 0;
		double EPS = 1e-2;
		while (up - down > EPS) {
			double mid = (up + down) / 2.;
			if (!can(mid)) {
				down = mid;
			} else {
				up = mid;
			}
		}
		double d = up;
		can(d);
		out.printf("%.6f\n", Math.round(d * 2) / 2.);
		for (double i : posAns) {
			out.printf("%.6f ", Math.round(i * 2) / 2.);
		}
		out.println();
		
	}
	
	private boolean can(double d) {
		double di = d * 2;
		double prev = x[0];
		double last = x[0];
		int res = 0;
		for (double xs : x) {			
			if (xs - prev > di ) {
				if (res == 2) {
					return false;
				}
				posAns[res] = (last + prev) / 2.;
				++res;
				prev = xs;				
			}
			last = xs;
		}
		posAns[2] = (x[x.length - 1] + prev) / 2.;
		return true;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		new Thread(new C()).start();

	}

	private BufferedReader br;
	private StringTokenizer st;
	private PrintWriter out;

	@Override
	public void run() {
		try {
			Locale.setDefault(Locale.US);
			if (Boolean.getBoolean("SPbAU")) {
				br = new BufferedReader(new FileReader("input.txt"));
			} else {
				br = new BufferedReader(new InputStreamReader(System.in));
			}
			st = new StringTokenizer("");
			out = new PrintWriter(System.out);
			while (hasNext()) {
				solve();
			}
			out.close();			
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(-1);
		}
		
	}

	
	
	String next() throws IOException {
		while (!st.hasMoreTokens()) {
			String temp = br.readLine();
			if (temp == null) {
				return null;
			}
			st = new StringTokenizer(temp);
		}
		return st.nextToken();
	}
	boolean hasNext() throws IOException {
		while (!st.hasMoreTokens()) {
			String temp = br.readLine();
			if (temp == null) {
				return false;
			}
			st = new StringTokenizer(temp);
		}
		return true;
	}

	int nextInt() throws IOException {
		return Integer.parseInt(next());
	}
	double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}
	long nextLong() throws IOException {
		return Long.parseLong(next());
	}
	
}