Boarding the High airplane
N passengers are boarding a plane that has exactly N seats. Each passenger holds a ticket for a specific seat, and all tickets are unique. However, some passengers are unpredictable. As passengers board the plane one at a time, the unpredictable ones ignore their tickets and choose a seat randomly from those available. In contrast, the normal passengers will sit in the seat assigned to them by their ticket. If a normal passenger finds their seat already taken, they will choose any available seat at random, with each option being equally likely. Your task is to calculate the probability that each passenger will end up sitting in the seat specified on their ticket.
Constraints
N is an integer where 1 ≤ N ≤ 100000.
Input
The first line contains the integer N. The second line contains N integers, each representing a passenger in the order they board the plane (0 indicates a normal passenger, 1 indicates an unpredictable passenger).
Output
Output N numbers, each representing the probability that the corresponding passenger will sit in their assigned seat. Each probability must be given with a precision of at least 10^{-8}.