CF1578G.Game of Chance

The King wants to marry off his daughter, and he wants her husband to have the greatest innate luckiness possible. To find such a person he decided to hold a heads-or-tails tournament.

If person $A$ with luckiness $x$ and person $B$ with luckiness $y$ play heads-or-tails against each other, person $A$ wins with probability $x/(x+y)$.

The tournament has several rounds. Each round some participants are split into pairs. Each pair plays against each other, and the loser leaves the tournament.

The participants are numbered from $1$ to $n$. During the first round, a number $k$ ($1 \le k \le n$) is selected such that $n-k/2$ is a power of $2$ (such $k$ always exists and is unique). Only participants numbered from $1$ to $k$ take part in the first round. It ensures that in all other rounds the number of participants is the power of $2$.

During other rounds, all the participants who still have not left the tournament take part. If during some round, participants numbered $p_1 \lt \ldots \lt p_{2m}$ take part, then they are split into pairs in the following manner: participant $p_{2i-1}$ plays against participant $p_{2i}$ for each $i$ from $1$ to $m$.

The rounds are held until only one participant is left. He is declared the winner of the tournament and he will marry the King's daughter. The princess can't wait to find out who is her future husband. She asked every participant to tell her his luckiness. Assuming they did not lie, she wants to know the probability of each participant winning the tournament. As you are the best friend of the princess, she asks you to help her.

国王想为女儿择婿，希望女婿拥有尽可能高的先天幸运值。为此，他决定举办一场抛硬币锦标赛。

若幸运值为 $x$ 的人 $A$ 与幸运值为 $y$ 的人 $B$ 进行抛硬币对决，则 $A$ 获胜的概率为 $x/(x+y)$。

该锦标赛包含若干轮次。每轮中，部分参赛者被两两配对；每对选手进行对决，败者退出锦标赛。

参赛者编号为 $1$ 至 $n$。在第一轮中，选择一个数 $k$（$1 \le k \le n$），使得 $n - k/2$ 是 $2$ 的幂（这样的 $k$ 总是存在且唯一）。仅编号为 $1$ 至 $k$ 的参赛者参加第一轮。此举保证了后续所有轮次中参赛者人数均为 $2$ 的幂。

在其余轮次中，所有尚未退出锦标赛的参赛者均参与。若某一轮中有 $2m$ 名参赛者，其编号按升序排列为 $p_1 < \ldots < p_{2m}$，则他们按如下方式配对：对每个 $i = 1, 2, \ldots, m$，参赛者 $p_{2i-1}$ 与 $p_{2i}$ 对决。

锦标赛持续进行，直至仅剩一名参赛者。该人即为锦标赛冠军，并将迎娶国王的女儿。公主迫不及待地想知道自己未来的丈夫是谁。她向每位参赛者询问了各自的幸运值。假设所有参赛者均如实作答，她希望知道每位参赛者赢得锦标赛的概率。作为公主最好的朋友，她请你协助完成这项任务。

The first line of the input contains the number of participants, $n$ ($2 \le n \le 3 \cdot 10^5$). The second line of the input contains $n$ integer numbers, $a_1, \ldots, a_{n}$ ($1 \le a_i \le 10^9$). The luckiness of the $i$-th participant equals to $a_i$.

输入的第一行包含参与者人数 $n$（$2 \le n \le 3 \cdot 10^5$）。输入的第二行包含 $n$ 个整数 $a_1, \ldots, a_{n}$（$1 \le a_i \le 10^9$）。第 $i$ 位参与者的幸运值为 $a_i$。

Print $n$ numbers $p_i$. The $i$-th number should be the probability of the $i$-th participant winning the tournament. The absolute error of your answer must not exceed $10^{-9}$.

输出 $n$ 个数字 $p_i$。其中第 $i$ 个数字应为第 $i$ 位参赛者赢得锦标赛的概率。你的答案的绝对误差不得超过 $10^{-9}$。

Here is an example of a tournament bracket, showing the winning probability in each pair.

以下是一个锦标赛对阵表的示例，其中显示了每对选手之间的获胜概率。