Relaxation by the River Junior
A couple has decided 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. His wife, Mary, is afraid of heights and prefers a location where the bank is as low as possible. They are driving along a one-way main road with N turns leading to the river. Each turn leads to a different spot by the river, and both know the height of each location. George is driving, but Mary can distract him so that he might miss the next turn, except for the last one (which George is aware of). All turns look alike, so George cannot tell which place each turn leads to as they approach. The main road continues past the last turn and also leads to a known location by the river. George can choose one of the following strategies: take the first turn he notices, the second, the third, and so on, or not turn at all. If he plans to take a certain number of turns but notices fewer, they will end up at the location at the end of the main road.
The task is to determine George's optimal strategy, considering that Mary will also act optimally.
**Constraints**
N and h_i are integers. 1 ≤ N ≤ 5000, 0 ≤ h_i ≤ 1000.
Input
The first line contains the number N. The second line contains N+1 numbers h_i, representing the height of the place reached from the i-th turn (h_{N+1} is the height of the location reached if no turns are taken).
Output
The first line should output the maximum average height of the place George can reach, given Mary's optimal opposition. The second line should output N+1 numbers — the probabilities with which George should apply each of his pure strategies to achieve this height. All values must be output with a precision of at least 10^{-6}. If there are multiple optimal strategies, 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 N-th turn, and so on.