C. Three Base Stationstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputThe 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.InputThe 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.OutputPrint 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.ExamplesInput41 2 3 4Output0.5000001.500000 2.500000 3.500000Input310 20 30Output010.000000 20.000000 30.000000Input510003 10004 10001 10002 1Output0.5000001.000000 10001.500000 10003.500000
Input41 2 3 4
Output0.5000001.500000 2.500000 3.500000
['binary search', 'greedy', '*1800']