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

public class C implements Runnable {
	private void solve() {
		int n = in.nextInt();
		int[] x = new int[n];
		for (int i = 0; i < n; ++i)
			x[i] = 2 * in.nextInt();
		Arrays.sort(x);
		int[] y = new int[n];
		int mm=0;
		for (int i=0; i<n; ++i) if (i == 0 || x[i-1] != x[i]){
			y[mm++]=x[i];
		}
		if (mm < 4) {
			out.println(0);
			out.print(y[0] / 2 + " ");
			if (mm < 2)
				out.print(y[0] / 2 + " ");
			else
				out.print(y[1] / 2 + " ");
			if (mm < 3)
				out.print(y[0] / 2 + " ");
			else
				out.print(y[2] / 2 + " ");
			return;
		}
		int l = 0, r = 1000000001, q1 = 0, q2 = 0, q3 = 0;
		while (l + 1 < r) {
			int m = (l + r) / 2;
			int p1 = x[0] + m;
			int p2 = p1, p3 = p1;
			int i = 0;
			boolean ok = true;
			while (i < n && x[i] - p1 <= m)
				++i;
			if (i < n) {
				p2 = x[i] + m;
				while (i < n && x[i] - p2 <= m)
					++i;
				if (i < n) {
					p3 = x[i] + m;
					while (i < n && x[i] - p3 <= m)
						++i;
					if (i < n)
						ok = false;
				}
			}
			if (ok) {
				r = m;
				q1 = p1;
				q2 = p2;
				q3 = p3;
			} else
				l = m;
		}

		out.printf("%.9f\n", r / 2.0);
		out.printf("%.9f %.9f %.9f\n", q1 / 2.0, q2 / 2.0, q3 / 2.0);
	}

	private InputReader in;
	private PrintWriter out;

	public static void main(String[] args) {
		new C().run();
	}

	public C() {
		Locale.setDefault(Locale.US);
		in = new InputReader(System.in);
		out = new PrintWriter(System.out);
	}

	public void run() {
		// int numTests = in.readInt();
		// for (int testNumber = 0; testNumber < numTests; testNumber++) {
		solve();
		// }
		out.close();
	}

	static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar, numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		private int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public String nextString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuffer res = new StringBuffer();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private String readLine0() {
			StringBuffer buf = new StringBuffer();
			int c = read();
			while (c != '\n' && c != -1) {
				buf.appendCodePoint(c);
				c = read();
			}
			return buf.toString();
		}

		public String nextLine() {
			String s = readLine0();
			while (s.trim().length() == 0)
				s = readLine0();
			return s;
		}

		public String nextLine(boolean ignoreEmptyLines) {
			if (ignoreEmptyLines)
				return nextLine();
			else
				return readLine0();
		}

		public BigInteger nextBigInteger() {
			try {
				return new BigInteger(nextString());
			} catch (NumberFormatException e) {
				throw new InputMismatchException();
			}
		}

		public char nextCharacter() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			return (char) c;
		}

		public double nextDouble() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			double res = 0;
			while (!isSpaceChar(c) && c != '.') {
				if (c < '0' || c > '9') {
					if (c == 'e' || c == 'E') {
						int e = nextInt();
						return res * Math.pow(10, e);
					}
					throw new InputMismatchException();
				}
				res *= 10;
				res += c - '0';
				c = read();
			}
			if (c == '.') {
				c = read();
				double m = 1;
				while (!isSpaceChar(c)) {
					if (c == 'e' || c == 'E') {
						int e = nextInt();
						return res * Math.pow(10, e);
					}
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					m /= 10;
					res += (c - '0') * m;
					c = read();
				}
			}
			return res * sgn;
		}
	}
}