Boarding on the Junior Plane#4580
passengers are boarding a plane that has exactly seats. Each passenger has a ticket for a specific seat, and all tickets are unique. However, some passengers are mad. Passengers board the plane one by one, in a given order.
A mad passenger ignores the seat number on their ticket and chooses a random available seat, each with equal probability. A normal passenger will sit in the seat indicated on their ticket if it is free; otherwise, to avoid conflict, they choose any available seat at random, each with equal probability.
For each passenger, determine the probability that they will occupy their assigned seat upon entering the plane.
Constraints
is an integer, 1 \leq N \leq 15.
The first line contains the integer .
The second line contains integers. Each value indicates the type of the corresponding passenger in boarding order ( for a normal passenger, for a mad passenger).
Output numbers, each representing the probability that the corresponding passenger will sit in their assigned seat. Print each value with an accuracy of at least 10^{-8}.
Example 1