Bessie's Balancing Act

Bessie is performing on a balance beam consisting of positions labeled from \(0, 1, \ldots, N+1\). If she ever reaches position \(0\) or \(N+1\), she falls off and earns a reward of 0. At any position \(k\) (with \(1 \le k \le N\)), she may choose one of the following actions:

1. Flip a fair coin. If it lands heads she moves to \(k+1\); if tails, she moves to \(k-1\). (Each possibility has probability \(\frac12\).)
2. Jump off the beam and receive an immediate reward of \(f(k)\) (where \(0 \le f(k) \le 10^9\)).

Since the outcome from flipping a coin is random, Bessie cannot guarantee a specific reward. However, by choosing her actions optimally at every step, she can maximize her expected reward. Let \(V(k)\) be the maximum expected reward obtainable from position \(k\) if she plays optimally. Then the Bellman equation is:

[ V(k) = \max\Bigl{ f(k), ; \frac{V(k-1) + V(k+1)}{2} \Bigr}, \quad 1 \le k \le N, ]

with the boundary conditions \(V(0)=V(N+1)=0\).

Note that if Bessie chooses to flip the coin, the recurrence \(V(k-1)\) and \(V(k+1)\) apply. In regions where flipping is optimal, the equality \(V(k)=\frac{V(k-1)+V(k+1)}{2}\) forces \(V(k)\) to be linear. In other words, on maximal intervals where coin‐flipping is chosen over jumping off (i.e. when \(\frac{V(k-1)+V(k+1)}{2} \ge f(k)\)), \(V(k)\) is given by the linear interpolation between two positions where stopping (and thus taking \(f(\cdot)\)) is optimal. Therefore, the solution \(V(k)\) turns out to be the maximum over the immediate reward \(f(k)\) and a set of linear functions defined by pairs of "stopping" positions that are feasible. In particular, for any two indices \(l\) and \(r\) (with \(l

Your task is: Given \(N\), a starting position \(s\) (with \(1 \le s \le N\)) and the rewards \(f(1), f(2), \ldots, f(N)\), compute the maximum expected reward \(V(s)\) Bessie can obtain if she makes optimal decisions.

Input Format: The first line contains two integers \(N\) and \(s\). The second line contains \(N\) integers \(f(1), f(2), \ldots, f(N)\), separated by spaces.

Output Format: Output a single number — the maximum expected reward. Answers within an absolute or relative error of \(10^{-6}\) will be accepted.

inputFormat

The input consists of two lines:

• The first line contains two integers \(N\) and \(s\) (\(1 \le s \le N\)).
• The second line contains \(N\) integers \(f(1), f(2), \ldots, f(N)\) (\(0 \le f(k) \le 10^9\)).

outputFormat

Output a single number representing the maximum expected reward obtainable from position \(s\). Your answer will be accepted if the absolute or relative error is at most \(10^{-6}\).

sample

3 2
5 3 6

5.5