Firehose

A circular street runs through your neighbourhood. The street is a perfect circle whose circumference is exactly $1{,}000{,}000$, and there are $H$ houses ($1 \le H \le 1000$) along it.

Every point on the street is identified by its address: the clockwise arc-length from the northernmost point of the circle. The northernmost point has address $0$, so every address $a$ satisfies $0 \le a < 1{,}000{,}000$. No two houses share an address.

Your special fire hoses run along the curve of the street, so the length of hose needed to connect a house to a fire hydrant equals the arc-length between them measured along the street.

You may place $k$ fire hydrants ($1 \le k \le 1000$) anywhere on the street (a hydrant may sit at the same location as a house). Each house is then connected to its nearest hydrant. Place the hydrants so that the maximum hose length over all houses is as small as possible, and report that minimum possible maximum length.

The first line contains the integer $H$, the number of houses.

Each of the next $H$ lines contains one integer, the address of a house ($0 \le a < 1{,}000{,}000$). No two houses have the same address.

The following line contains the integer $k$, the number of fire hydrants you may place.

Print a single line with the smallest possible value of the maximum hose length, that is, the length of hose that lets every house reach its nearest hydrant when the hydrants are placed optimally.

This value is always a multiple of $0.5$. Print it as a plain integer when it is a whole number; otherwise print it with a single trailing fractional digit of $.5$ (for example, 5.5).