Посадка в самолет High
N человек садятся в самолет, в котором есть в точности N мест. У каждого из пассажиров есть билет на некоторое место в этом самолете и нет двух одинаковых билетов. Однако некоторые из пассажиров являются сумасшедшими. Люди заходят по одному в салон самолета. Сумасшедшие люди при входе в самолет не смотрят на билет, а садятся на некоторое место, выбирая его равновероятно из свободных, нормальные же люди занимают место, указанное в билете. Но если место нормального пассажира занято, то чтобы не начинать скандал, он садится на любое свободное место с равной вероятностью. Требуется определить для каждого пассажира вероятность того, что он займет при входе в самолет место, указанное в его билете.
Ограничения
N – целое число, 1 ≤ N ≤ 100000.
Входные данные
В первой строке задается число N. Во второй строке записаны N чисел, каждое из которых определяет соответствующего пассажира в порядке входа в салон самолета (0 обозначает нормального человека, 1 – сумасшедшего).
Выходные данные
Выведите N чисел, каждое из которых определяет вероятность того, что соответствующий пассажир займет свое место. Все значения должны быть выведены с точностью не меньше 10^{-8}.