Посадка у літак Junior#4580
пасажирів сідають у літак, у якому рівно місць. У кожного пасажира є квиток на конкретне місце, і всі квитки унікальні. Проте деякі пасажири неадекватні. Пасажири заходять у літак один за одним, у заданому порядку.
Неадекватний пасажир ігнорує номер місця у своєму квитку й вибирає випадкове вільне місце, кожне з однаковою ймовірністю. Нормальний пасажир займе місце, зазначене в його квитку, якщо воно вільне; інакше, щоб уникнути конфлікту, він вибирає будь-яке вільне місце випадковим чином, з однаковою ймовірністю.
Для кожного пасажира визначте ймовірність того, що він займе місце, зазначене у його квитку, коли сяде у літак.
Обмеження
— ціле число, 1 \leq N \leq 15.
У першому рядку міститься число .
У другому рядку — цілих чисел. Кожне значення позначає тип відповідного пасажира у порядку посадки ( — нормальний пасажир, — неадекватний пасажир).
Виведіть чисел — для кожного пасажира ймовірність того, що він посяде своє місце. Виведіть кожне значення з точністю не менше 10^{-8}.
Приклад 1