Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Three Base Stations

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard 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 *x*_{i} coordinate. The village consists of *n* houses, the *i*-th house is located in the point with coordinates of *x*_{i}.

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·10^{5}) which represents the number of houses in the village. The second line contains the coordinates of houses — the sequence *x*_{1}, *x*_{2}, ..., *x*_{n} of integer numbers (1 ≤ *x*_{i} ≤ 10^{9}). 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·10^{9} 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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/17/2018 07:15:38 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|