I. Speed Limit
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A one-way highway extends through the Kingdom of Icpca. The highway is divided from start to end into sections that are $$$1$$$ km long, and each section has its speed limit.

You are driving a vehicle and want to travel from the start to the end of this highway. The speed of the vehicle can be changed instantaneously at any time. In each change, you choose a non-negative integer $$$v$$$ and set the speed to $$$v$$$ km/h. If the speed before the change is $$$v'$$$ km/h, this change incurs a cost of $$$|v-v'|$$$. Before leaving the start, the speed of the vehicle is $$$0$$$ km/h. Also, at the moment the vehicle arrives at the end, the speed must be changed to $$$0$$$ km/h.

Find the minimum travel time from the start to the end such that the total incurred cost does not exceed the given cost limit and the vehicle does not exceed the speed limits in any sections

Input

The input contains one or more test cases, each in the following format.

$$$n$$$ $$$f$$$
$$$a_{1}$$$ $$$a_{2}$$$ $$$\cdots$$$ $$$a_{n}$$$

A test case consists of two lines. The first line contains two integers $$$n$$$ and $$$f$$$, where $$$n$$$ is the number of sections of the highway and $$$f$$$ is the limit of the total cost ($$$1 \leq n \leq 2 \times 10^5$$$, $$$2 \leq f \leq 10^{10}$$$). Here, $$$f$$$ is even. The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, representing the speed limits of the sections. For $$$i=1,2,\ldots,n$$$, the speed limit of the $$$i$$$-th section from the start is $$$a_i$$$ km/h ($$$1 \leq a_i \leq 10^5$$$).

The end of the input is indicated by a line containing two zeros. The number of test cases does not exceed $$$10^4$$$. The sum of $$$n$$$ over all the test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case, output in a line the minimum time in hours required to travel from the start to the end. The output is considered correct if the absolute or relative error does not exceed $$$10^{-4}$$$.

Example
Input
5 120
120 100 40 100 120
5 100
10 20 30 20 10
10 160
30 10 40 10 50 90 20 60 50 30
3 4
2 1 2
3 2
2 1 2
5 20
7 3 8 4 9
15 14
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
15 60
6 2 3 5 1 7 2 1 5 9 7 5 3 2 6
0 0
Output
0.1050000000
0.3333333333
0.4776190476
2.5000000000
3.0000000000
1.1166666667
5.3285714286
5.4968253968
Note

In the first test case of Sample Input 1, the minimum time can be achieved by changing the speed of the vehicle as follows.

  1. At the start, change the speed of the vehicle to $$$50$$$ km/h. This incurs a cost of $$$|50-0|=50$$$.
  2. Pass through the first and second sections at $$$50$$$ km/h. This takes $$$2/50=1/25$$$ hours.
  3. Immediately after passing through the second section, change the speed to $$$40$$$ km/h. This incurs a cost of $$$|40-50|=10$$$.
  4. Pass through the third section at $$$40$$$ km/h. This takes $$$1/40$$$ hours.
  5. Immediately after passing through the third section, change the speed to $$$50$$$ km/h. This incurs a cost of $$$|50-40|=10$$$.
  6. Pass through the fourth and fifth sections at $$$50$$$ km/h. This takes $$$2/50=1/25$$$ hours.
  7. Upon arriving at the end, change the speed to $$$0$$$ km/h. This incurs a cost of $$$|0-50|=50$$$.

The total cost is $$$50+10+10+50=120$$$. The total time is $$$1/25 + 1/40 + 1/25 = 0.105$$$ hours.