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