Отдых у реки 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-го поворота, и т.д.