I. Minimax Limit
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Min and Max have a continuous piecewise linear function $$$f(x)$$$. The function $$$f(x)$$$ is defined on the segment $$$[0, n]$$$ as follows:

  • if $$$x \in [0, n]$$$ is an integer, then $$$f(x) = a_x$$$;
  • otherwise, if $$$k = \lfloor x \rfloor$$$, then $$$f(x) = f(k) + (x - k)(f(k + 1) - f(k))$$$.

Min and Max are playing a game. Before the game starts they choose two positive real parameters $$$A$$$ and $$$\varepsilon$$$. There is a counter $$$T$$$ initially equal to $$$A$$$. Before the game starts, Max chooses an arbitrary real number $$$x \in [0, n]$$$. Players then proceed to take turns starting from Min. During a player's turn:

  • if $$$T \leq 0$$$, the game is over;
  • the player can change $$$x$$$ to any real number $$$x' \in [0, n]$$$ such that $$$|x - x'| \leq T$$$;
  • $$$T$$$ is decreased by $$$\varepsilon$$$.

When the game is over, the result of the game is equal to $$$f(x)$$$. Min wants to minimize the result, while Max wants to maximize it.

Let $$$R(A, \varepsilon)$$$ be the result of the game with parameters $$$A$$$ and $$$\varepsilon$$$ if both players play optimally. Compute $$$\displaystyle \lim_{\varepsilon \to 0} R(A, \varepsilon)$$$. It is guaranteed that this limit exists.

Input

The first line contains two integers $$$n$$$ and $$$A$$$ ($$$1 \leq A \leq n \leq 100\,000$$$).

The second line contains $$$n + 1$$$ integers $$$a_0, \ldots, a_n$$$ ($$$-10^6 \leq a_i \leq 10^6$$$).

Output

Print a single real number $$$\displaystyle \lim_{\varepsilon \to 0} R(A, \varepsilon)$$$. Your answer will be accepted if its absolute or relative error does not exceed $$$10^{-4}$$$.

Examples
Input
1 1
0 1
Output
0.5000000000
Input
2 1
0 2 1
Output
1.4285714283