#include <bits/stdc++.h>
using namespace std;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
template <class T>
void initArray(T *arr, int size, T value) {
  for (int i = 0; i < size; i++) {
    arr[i] = value;
  }
}
template <class T>
T readValue(string s) {
  T result;
  istringstream sin(s);
  sin >> result;
  return result;
}
template <class T>
inline T gcd(T a, T b) {
  return (!a) ? b : gcd(b % a, a);
}
template <class T>
inline T mod(T a, T p) {
  a %= p;
  return (a < 0) ? a + p : a;
}
template <class T>
inline int numbits(T n) {
  return (!n) ? 0 : 1 + numbits(n & (n - 1));
}
template <class T>
inline T inverse(T a, T m) {
  a = mod<T>(a, m);
  return (a == 1) ? 1 : mod((1 - m * inverse(m % a, a)) / a, m);
}
template <class T>
inline bool isPrime(T a) {
  T lim = (T)sqrt((double)a);
  for (T i = 2; i < lim; i++)
    if (a % i == 0) return false;
  return true;
}
template <class T>
inline T power(T a, T p, T mod) {
  if (!p) return 1;
  T temp = power(a, p >> 1, mod);
  temp = (temp * temp) % mod;
  if (p & 1) temp = (temp * a) % mod;
  return temp;
}
void get_primes(int start, int end, vector<int> &vi) {
  int *p = new int[end + 1];
  initArray<int>(p, end + 1, 0);
  p[1] = 1;
  for (int i = 2; i <= end; i++) {
    if (!p[i]) {
      if (i >= start) vi.push_back(i);
      for (int j = 2 * i; j <= end; j += i) p[j] = 1;
    }
  }
}
bool dfs(int current, int final, int total, int *visited, int **edges,
         bool flow) {
  if (current == final) return true;
  if (visited[current]) return false;
  visited[current] = true;
  for (int i = 0; i < total; i++)
    if (edges[current][i] && dfs(i, final, total, visited, edges, flow)) {
      if (flow) {
        edges[current][i]--;
        edges[i][current]++;
      }
      return true;
    }
  return false;
}
int flow(int in, int out, int total, int **edges) {
  int result = 0;
  int *visited = new int[total];
  while (initArray<int>(visited, total, 0),
         dfs(in, out, total, visited, edges, true))
    result++;
  return result;
}
void create_set(int x, int *P, int *rank) {
  P[x] = x;
  rank[x] = 0;
}
int find_set(int x, int *P) {
  if (x != P[x]) P[x] = find_set(P[x], P);
  return P[x];
}
bool merge_sets(int x, int y, int *P, int *rank) {
  int Px = find_set(x, P);
  int Py = find_set(y, P);
  if (Px == Py) return false;
  if (rank[Px] > rank[Py])
    P[Py] = Px;
  else
    P[Px] = Py;
  if (rank[Px] == rank[Py]) rank[Py]++;
  return true;
}
int read_cum_freq(int index, int *tree) {
  int sum = 0;
  while (index) {
    sum += tree[index];
    index -= (index & -index);
  }
  return sum;
}
void upd_freq(int index, int mxIndex, int value, int *tree) {
  while (index <= mxIndex) {
    tree[index] += value;
    index += (index & -index);
  }
}
int read_freq(int index, int *tree) {
  return read_cum_freq(index, tree) - read_cum_freq(index - 1, tree);
}
void build_failure_function(const string &str, int *temp_arr) {
  temp_arr[0] = temp_arr[1] = 0;
  for (int i = 2; i <= static_cast<int>(str.size()); i++) {
    temp_arr[i] = -1;
    for (int ind = temp_arr[i - 1]; temp_arr[i] == -1; ind = temp_arr[ind]) {
      if (str[ind] == str[i - 1]) {
        temp_arr[i] = ind + 1;
      } else if (ind == 0) {
        temp_arr[i] = 0;
      }
    }
  }
}
void KMP(const string &s1, const string &s2, int *res) {
  int *temp_arr = new int[s2.size() + 1];
  build_failure_function(s2, temp_arr);
  int i = 0;
  int ind = 0;
  while (i < static_cast<int>(s1.size())) {
    if (s1[i] == s2[ind]) {
      res[i] = ++ind;
      if (res[i] == s2.size()) {
        ind = temp_arr[ind - 1];
      }
      i++;
    } else if (ind == 0) {
      res[i++] = 0;
    } else {
      ind = temp_arr[ind];
    }
  }
  delete[] temp_arr;
}
void setup(int value) {
  freopen("input.txt", "r", stdin);
  if (value) {
    freopen("output.txt", "w", stdout);
  }
}
int main() {
  int n;
  cin >> n;
  vector<int> vi;
  for (int i = 0; i < n; i++) {
    int val;
    cin >> val;
    vi.push_back(val);
  }
  sort(vi.begin(), vi.end());
  double low = 0;
  double high = 1000000000;
  for (int i = 0; i < 100; i++) {
    double md = (low + high);
    bool pos = true;
    int val1 = 0;
    int val2 = vi.size() - 1;
    while (val1 < vi.size() && (double)(vi[val1] - vi[0]) <= md + 1E-9) val1++;
    while (val2 >= 0 && (double)(vi.back() - vi[val2]) <= md + 1E-9) val2--;
    if (val1 < val2 && (double)(vi[val2] - vi[val1]) > md + 1E-9) {
      pos = false;
    }
    if (pos)
      high = md * 0.5;
    else
      low = md * 0.5;
  }
  printf("%.6f\n", high);
  vector<double> arr(3, 0);
  arr[0] = high + vi[0];
  int val1 = 0;
  int val2 = vi.size() - 1;
  while (val1 < vi.size() && (double)(vi[val1] - vi[0]) <= 2.0 * high + 1E-9)
    val1++;
  while (val2 >= 0 && (double)(vi.back() - vi[val2]) <= 2.0 * high + 1E-9)
    val2--;
  if (val1 <= val2)
    arr[1] = (double)(vi[val1] + vi[val2]) * 0.5;
  else
    arr[1] = arr[0];
  arr[2] = -high + vi.back();
  sort(arr.begin(), arr.end());
  for (int i = 0; i < 3; i++) printf("%.6f ", arr[i]);
  std::cout << std::endl;
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
template <class T>
void initArray(T *arr, int size, T value) {
  for (int i = 0; i < size; i++) {
    arr[i] = value;
  }
}
template <class T>
T readValue(string s) {
  T result;
  istringstream sin(s);
  sin >> result;
  return result;
}
template <class T>
inline T gcd(T a, T b) {
  return (!a) ? b : gcd(b % a, a);
}
template <class T>
inline T mod(T a, T p) {
  a %= p;
  return (a < 0) ? a + p : a;
}
template <class T>
inline int numbits(T n) {
  return (!n) ? 0 : 1 + numbits(n & (n - 1));
}
template <class T>
inline T inverse(T a, T m) {
  a = mod<T>(a, m);
  return (a == 1) ? 1 : mod((1 - m * inverse(m % a, a)) / a, m);
}
template <class T>
inline bool isPrime(T a) {
  T lim = (T)sqrt((double)a);
  for (T i = 2; i < lim; i++)
    if (a % i == 0) return false;
  return true;
}
template <class T>
inline T power(T a, T p, T mod) {
  if (!p) return 1;
  T temp = power(a, p >> 1, mod);
  temp = (temp * temp) % mod;
  if (p & 1) temp = (temp * a) % mod;
  return temp;
}
void get_primes(int start, int end, vector<int> &vi) {
  int *p = new int[end + 1];
  initArray<int>(p, end + 1, 0);
  p[1] = 1;
  for (int i = 2; i <= end; i++) {
    if (!p[i]) {
      if (i >= start) vi.push_back(i);
      for (int j = 2 * i; j <= end; j += i) p[j] = 1;
    }
  }
}
bool dfs(int current, int final, int total, int *visited, int **edges,
         bool flow) {
  if (current == final) return true;
  if (visited[current]) return false;
  visited[current] = true;
  for (int i = 0; i < total; i++)
    if (edges[current][i] && dfs(i, final, total, visited, edges, flow)) {
      if (flow) {
        edges[current][i]--;
        edges[i][current]++;
      }
      return true;
    }
  return false;
}
int flow(int in, int out, int total, int **edges) {
  int result = 0;
  int *visited = new int[total];
  while (initArray<int>(visited, total, 0),
         dfs(in, out, total, visited, edges, true))
    result++;
  return result;
}
void create_set(int x, int *P, int *rank) {
  P[x] = x;
  rank[x] = 0;
}
int find_set(int x, int *P) {
  if (x != P[x]) P[x] = find_set(P[x], P);
  return P[x];
}
bool merge_sets(int x, int y, int *P, int *rank) {
  int Px = find_set(x, P);
  int Py = find_set(y, P);
  if (Px == Py) return false;
  if (rank[Px] > rank[Py])
    P[Py] = Px;
  else
    P[Px] = Py;
  if (rank[Px] == rank[Py]) rank[Py]++;
  return true;
}
int read_cum_freq(int index, int *tree) {
  int sum = 0;
  while (index) {
    sum += tree[index];
    index -= (index & -index);
  }
  return sum;
}
void upd_freq(int index, int mxIndex, int value, int *tree) {
  while (index <= mxIndex) {
    tree[index] += value;
    index += (index & -index);
  }
}
int read_freq(int index, int *tree) {
  return read_cum_freq(index, tree) - read_cum_freq(index - 1, tree);
}
void build_failure_function(const string &str, int *temp_arr) {
  temp_arr[0] = temp_arr[1] = 0;
  for (int i = 2; i <= static_cast<int>(str.size()); i++) {
    temp_arr[i] = -1;
    for (int ind = temp_arr[i - 1]; temp_arr[i] == -1; ind = temp_arr[ind]) {
      if (str[ind] == str[i - 1]) {
        temp_arr[i] = ind + 1;
      } else if (ind == 0) {
        temp_arr[i] = 0;
      }
    }
  }
}
void KMP(const string &s1, const string &s2, int *res) {
  int *temp_arr = new int[s2.size() + 1];
  build_failure_function(s2, temp_arr);
  int i = 0;
  int ind = 0;
  while (i < static_cast<int>(s1.size())) {
    if (s1[i] == s2[ind]) {
      res[i] = ++ind;
      if (res[i] == s2.size()) {
        ind = temp_arr[ind - 1];
      }
      i++;
    } else if (ind == 0) {
      res[i++] = 0;
    } else {
      ind = temp_arr[ind];
    }
  }
  delete[] temp_arr;
}
void setup(int value) {
  freopen("input.txt", "r", stdin);
  if (value) {
    freopen("output.txt", "w", stdout);
  }
}
int main() {
  int n;
  cin >> n;
  vector<int> vi;
  for (int i = 0; i < n; i++) {
    int val;
    cin >> val;
    vi.push_back(val);
  }
  sort(vi.begin(), vi.end());
  double low = 0;
  double high = 1000000000;
  for (int i = 0; i < 100; i++) {
    double md = (low + high);
    bool pos = true;
    int val1 = 0;
    int val2 = vi.size() - 1;
    while (val1 < vi.size() && (double)(vi[val1] - vi[0]) <= md + 1E-9) val1++;
    while (val2 >= 0 && (double)(vi.back() - vi[val2]) <= md + 1E-9) val2--;
    if (val1 < val2 && (double)(vi[val2] - vi[val1]) > md + 1E-9) {
      pos = false;
    }
    if (pos)
      high = md * 0.5;
    else
      low = md * 0.5;
  }
  printf("%.6f\n", high);
  vector<double> arr(3, 0);
  arr[0] = high + vi[0];
  int val1 = 0;
  int val2 = vi.size() - 1;
  while (val1 < vi.size() && (double)(vi[val1] - vi[0]) <= 2.0 * high + 1E-9)
    val1++;
  while (val2 >= 0 && (double)(vi.back() - vi[val2]) <= 2.0 * high + 1E-9)
    val2--;
  if (val1 <= val2)
    arr[1] = (double)(vi[val1] + vi[val2]) * 0.5;
  else
    arr[1] = arr[0];
  arr[2] = -high + vi.back();
  sort(arr.begin(), arr.end());
  for (int i = 0; i < 3; i++) printf("%.6f ", arr[i]);
  std::cout << std::endl;
  return 0;
}

```