eolymp
bolt
Try our new interface for solving problems
Problems

Посадка в самолет Junior

Посадка в самолет Junior

Time limit 1 second
Memory limit 256 MiB

N человек садятся в самолет, в котором есть в точности N мест. У каждого из пассажиров есть билет на некоторое место в этом самолете и нет двух одинаковых билетов. Однако некоторые из пассажиров являются сумасшедшими. Люди заходят по одному в салон самолета. Сумасшедшие люди при входе в самолет не смотрят на билет, а садятся на некоторое место, выбирая его равновероятно из свободных, нормальные же люди занимают место, указанное в билете. Но если место нормального пассажира занято, то чтобы не начинать скандал, он садится на любое свободное место с равной вероятностью. Требуется определить для каждого пассажира вероятность того, что он займет при входе в самолет место, указанное в его билете.

Ограничения

N – целое число, 1N15.

Input data

В первой строке задается число N. Во второй строке записаны N чисел, каждое из которых определяет соответствующего пассажира в порядке входа в салон самолета (0 обозначает нормального человека, 1 – сумасшедшего).

Output data

Выведите N чисел, каждое из которых определяет вероятность того, что соответствующий пассажир займет свое место. Все значения должны быть выведены с точностью не меньше 10^{-8}.

Examples

Input example #1
3
0 1 0
Output example #1
1.00000000 0.50000000 0.50000000