Relaxation by the High River#4569
A couple is planning to spend their vacation by the river. George enjoys high places and wants to find a spot where the riverbank is as high as possible above the river level. His wife, Mary, is afraid of heights and prefers a location where the bank is as low as possible. As they drive along a one-way main road, there are turns leading to the river. Each turn leads to a spot with a known height above the river.
George is driving, but Mary can distract him so that he might miss the next turn, except for the last one (which George always notices). All the turns look alike, so when approaching a turn, George cannot tell which place he will end up at until he takes it. The main road continues past the last turn and leads to another spot by the river with a known height.
It is clear that George can use one of the following strategies: take the first turn he notices, the second such turn, the third, and so on, or not turn at all. Of course, if it happens that he notices fewer turns than his intended strategy requires, the couple will end up at the spot at the end of the main road.
Your task is to determine the optimal strategy for George, assuming that Mary also acts optimally.
Constraints
and h_i are integers. 1 \leq N \leq 10^5, 0 \leq h_i \leq 1000.
The first line contains the number . The second line contains N+1 integers h_i, denoting the height of the place reached by the -th strategy (h_{N+1} is the height of the place reached if no turns are taken).
On the first line, output the maximum average height George can achieve, considering Mary's optimal opposition. On the second line, output N+1 numbers — the probabilities with which George should employ each of his pure strategies to achieve this height. All values must be presented with a precision of at least 10^{-6}.
If multiple optimal strategies exist, choose the one with the highest probability of selecting the "Do not turn anywhere" strategy. If there are still ties, choose the one with the highest probability of selecting the -th turn, and so on.
Example 1