Problem G
Sky's the Limit
Unfortunately, all is not well in Eagleton: the citizens have a bit of an envy problem. Every day, one random citizen (the owner of house $i$, let’s say) emerges from their house and compares their house’s height to the heights of the two neighboring houses. If house $i$ is at least as tall as the average, plus $k$ inches (in other words, if $h_ i \geq (h_{i-1} + h_{i+1}) / 2 + k$), the citizen retreats back into their house, satisfied. Otherwise, the citizen remodels their house to have new height $(h_{i-1} + h_{i+1}) / 2 + k$. (The citizen does this remodeling even if the new height is only a tiny fraction of an inch taller than the old height—like we said, Eagleton has an envy problem.)
The left of house $1$ and the right of house $N$ is a nature preserve; the citizens of these houses treat the preserve as a “house” having height zero inches, for the purposes of the above calculations.
The city council of Eagleton is fed up with the constant construction traffic and noise, and has hired you to compute what Eagleton will look like when all of the remodeling is finally over. After some calculations, you discover that it is guaranteed that each house will converge to a final finite height after infinitely many days of the above remodeling process. Print the final height of the house that ends up tallest.
Input
The first line of input consists of an integer $N$ and real number $k$, separated by a space $(1 \leq N \leq 100\, 000; 0 \leq k \leq 10^{20})$: the number of houses in Eagleton and the number of inches each citizen wants their own house to be taller than the average of their neighbors.
$N$ lines follow. The $i$th such line (starting at $i=1$) contains a real number $h_ i$ ($0 \leq h_ i \leq 10^{20}$), the initial height (in inches) of house $i$.
The real numbers in the input may be provided in scientific notation (see for instance Sample Input 2) and will have at most ten digits after the decimal point.
Output
Print the height (in inches) of the tallest house, after all houses have been remodeled over infinitely many days of the process described above. Your answer will be judged correct if the absolute or relative error is within $10^{-6}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 39 10 40 |
40.5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 0.1 1.01e6 1.0e3 100 20.45 0 |
1010000 |
