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.*;
import java.util.*;

//Codeforces Beta Round #48 (Div. 1), C
public class ThreeBaseStations {

	public static void main(String[] args) throws IOException {
		File file = new File("input.txt");
		if(file.exists())
			System.setIn(new FileInputStream(file));
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(r.readLine()), a[] = new int[n];
		String ss[] = r.readLine().split(" ");
		assert ss.length == n;
		for(int i = 0; i < n; i++)
			a[i] = Integer.parseInt(ss[i]);

		List<Integer> list = new ArrayList<Integer>(a.length);
		for(int i : a)
			list.add(i);
		Set<Integer> set = new TreeSet<Integer>(list);
		list = null;
		Integer b[] = set.toArray(new Integer[0]);
		set = null;
		n = b.length;
		a = new int[n];
		for(int i = 0; i < n; i++)
			a[i] = b[i];
		b = null;

		int d = (a[n - 1] - a[0]) / 3 + 1, result[] = new int[3], z = 1;
		if(n <= 3) {
			d = 0;
			for(int i = 0; i < n; i++)
				result[i] = a[i];
		} else {
			for(int lo = 1, hi = n - 1; lo <= hi;) {
				int i = (hi + lo) / 2;
				int d1 = a[i] - a[0], d2 = a[n - 1] - a[n - 1 - i];
				boolean o = false;
				for(int td : new int[]{d1, d2}) {
					if(td > d)
						continue;
					int start = a[i] - a[0] <= td ? i + 1 : 1;
					for(; start < n; start++) {
						if(a[start] > a[0] + td)
							break;
					}
					int end = a[n - 1] - a[n - 1 - i] <= td ? n - 2 - i : n - 2;
					for(; end >= 0; end--) {
						if(a[end] < a[n - 1] - td)
							break;
					}
					if(a[end] - a[start] <= td) {
						z = i;
						d = td;
						o = true;
					}
				}
				if(o)
					hi = i - 1;
				else
					lo = i + 1;
			}
			for(int lo = Math.min(a[z - 1] - a[0], a[n - 1] - a[n - z]) + 1, hi = d; lo <= hi;) {
				int td = (hi + lo) / 2;
				int start = 1;
				for(; start < n; start++) {
					if(a[start] > a[0] + td)
						break;
				}
				int end = n - 2;
				for(; end >= 0; end--) {
					if(a[end] < a[n - 1] - td)
						break;
				}
				if(a[end] - a[start] <= td) {
					d = td;
					result[0] = a[0];
					result[1] = a[end] + a[start];
					result[2] = a[n - 1];
					hi = td - 1;
				} else
					lo = td + 1;
			}
		}
		System.out.printf("%f\n%f %f %f\n", d / 2., result[0] + d / 2., d != 0 ? result[1] / 2. : result[1], result[2] - d / 2.);
	}

}