Відпочинок біля річки High#4569
Пара планує провести відпустку біля річки. Джордж полюбляє височини і хоче знайти місце, де берег якомога вище над рівнем води. Його дружина Мері боїться висоти, і вважає за краще місце, де берег якомога нижчий. Вони їдуть по односторонній головній дорозі, де є поворотів до річки. Кожен поворот веде до місця з відомою висотою над річкою.
Джордж за кермом, але Мері може відволікти його, тож він може пропустити наступний поворот, окрім останнього (який Джордж завжди помічає). Всі повороти виглядають однаково, тож наближаючись до повороту, Джордж не може визначити, куди він потрапить, доки не зверне. Головна дорога продовжується за останнім поворотом і приводить до ще одного місця біля річки з відомою висотою.
Ясно, що Джордж може використати одну з наступних стратегій: звернути на перший помічений поворот, на другий, третій і так далі, або взагалі не звертати. Звісно, якщо він помітить менше поворотів, ніж вимагає його стратегія, пара опиниться в кінцевій точці маршруту.
Ваше завдання — визначити оптимальну стратегію для Джорджа, враховуючи, що Мері також діє оптимально.
Обмеження
і h_i — цілі числа. 1 \le N \le 10^5, 0 \le h_i \le 1000.
Перший рядок містить число . Другий рядок містить N+1 цілих чисел h_i, які позначають висоту місця, до якого призведе -та стратегія (h_{N+1} — висота місця, якщо не звертати ніде).
У першому рядку виведіть максимальну середню висоту, яку може отримати Джордж за умови оптимальної протидії Мері. У другому рядку виведіть N+1 чисел — ймовірності, з якими Джордж має використати кожну з чистих стратегій, щоб досягти цієї висоти. Всі значення мають бути представлені з точністю не менше 10^{-6}.
Якщо існує кілька оптимальних стратегій, оберіть ту, у якої ймовірність обрати стратегію «Не звертати» є найбільшою. Якщо залишаються ще кілька варіантів, оберіть ту, у якої ймовірність вибору -го повороту є найбільшою, і так далі.
Приклад 1