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