Відпочинок біля річки Junior
Сімейна пара вирішила провести відпочинок на березі річки. Джордж любить високі місця і хоче доїхати туди, де берег буде якоможга вище над рівнем річки. Його дружина Мері навпаки боїться висоти і хоче провести відпочинок там, де берег буде якомога нижче. Тепер же вони їдуть на машині по одностороній головній дорозі, вздовж якої є N поворотів до річки. Дорога за кожним з цих поворотів веде до річки і кажен з подружжя знає висоту, на якій розміщено місце, до якого веде відповідна дорога. За рулем зрозуміло Джордж, але Мері може відволікати Джодрджа так, що той може не помітити чергового повороту за винятком останнього повороту (і Джордж знає про це). Усі повороти настільки схожі, що підїзджаючи до чергового Джордж не може точно знати до якого місця він виводить. Головна дорога продовжується і за останнім поворотом і також веде до місця біля річки з відомою висотою берега. Очевидно, що Джордж може застосувати одну з наступних стратегій: повернути на першому поміченому ним повороті, повернути на другому з таких поворотів, повернути на третьому і т.д., або взагалі не звертати (зрозуміло у випадку, якщо виявиться що в дійсності він помітить менше поворотів, ніж вимагається у наміченій ним стратегії, пара прибуде у місце, розміщене в кінці головної дороги).
Потрібно визначити оптимальную стратегію для Джорджа у припущенні, що Мері також буде діяти оптимально.
Обмеження
N, h_i – цілі числа. 1 ≤ N ≤ 5000, 0 ≤ h_i ≤ 1000.
Вхідні дані
У першому рядку міститься число N. У другому рядку записано N+1 чисел h_i, які визначають висоту місця, до якого веде дорога від i-го повороту (h_{N+1} – висота місця, до якого виводить голавна дорога, якщо нікуди з неї не звертати).
Вихідні дані
Виведіть у першому рядку максимальну середню висоту місця, до якого може дістатись Джордж, при оптимальній протидії Мері. У дрцгому рядку виведіть N+1 число – ймовірності з якими Джордж повинен застосовувати кожну із своїх чистих стратегій для досягнення цієї висоти. Усі величини повинні виводитись з точністю не менше 10^{-6}. У випадку якщо існує декілька оптимальних стратегій, слід вибирати ту з них, у якої ймовірність вибору стратегії "Ніде не повертати" максимальна. Якщо і таких декілька – ту, яка має найбільшу ймовірність вибору N-го повороту, і т.д.