Relaxation by the High River
A couple is planning to spend their vacation by the river. George loves high places and wants to find a spot where the riverbank is as high as possible above the river level. On the other hand, 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 N 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 is aware of). All the turns look alike, so George cannot tell which place each turn leads to until he takes it. The main road continues past the last turn and also leads to a spot by the river with a known height. George can choose one of the following strategies: take the first turn he sees, the second, the third, and so on, or not turn at all. If he chooses a strategy that requires more turns than he notices, they will end up at the spot at the end of the main road.
Your task is to determine the optimal strategy for George, assuming Mary will also act optimally.
**Constraints**
N and h_i are integers. 1 ≤ N ≤ 10^5, 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 place reached if no turns are taken).
Output
Output the maximum average height George can achieve, considering Mary's optimal opposition, on the first line. 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 N-th turn, and so on.