国王想要把自己的女儿嫁出去,他希望她的丈夫拥有最大的先天幸运。为了找到这样的人,他决定举办一场正面或反面锦标赛。
如果运气好 $$$x$$$ 的人 $$$A$$$ 和运气好 $$$y$$$ 的人 $$$B$$$ 正面对决,则人 $$$A$$$ 以 $$$x/(x+y)$$$ 的概率获胜。
锦标赛有几轮。每轮一些参与者被分成两人一组。每对选手互相比赛,失败者退出比赛。
参与者编号从 $$$1$$$ 到 $$$n$$$。在第一轮中,选择一个数字 $$$k$$$ ($$$1 \le k \le n$$$),使得 $$$n-k/2$$$ 是 $$$2$$$ 的幂(这样的 $$$k$$$ 总是存在并且是唯一的)。只有编号从 $$$1$$$ 到 $$$k$$$ 的参与者才能参加第一轮。它确保在所有其他轮次中,参与者的数量是 $$$2$$$ 的幂。
在其他轮次中,所有尚未离开比赛的参赛者都会参加。如果在某一轮中,编号为 $$$p_1 < \ldots < p_{2m}$$$ 的参与者参加,则按以下方式将他们分成对:参与者 $$$p_{2i-1}$$$ 与参与者 $$$p_{2i}$$$ 进行比赛,每个 $$$i$$$ 从 $$$1$$$ 到 $$$m$$$。
轮次将持续到只剩下一名参与者为止。他被宣布为锦标赛的获胜者,并将娶国王的女儿。公主迫不及待地想知道谁是她未来的丈夫。她要求每位参与者告诉她他的幸运。假设他们没有撒谎,她想知道每个参与者赢得比赛的概率。由于你是公主最好的朋友,她请求你帮助她。
输入
输入的第一行包含参与者的数量 $$$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$$$。
输出
打印 $$$n$$$ 数字 $$$p_i$$$。第 $$$i$$$ 个数字应该是第 $$$i$$$ 个参与者赢得锦标赛的概率。您答案的绝对误差不得超过$$$10^{-9}$$$。
示例
输入 #1
5 1 4 1 1 4
输出 #1
0.026 0.3584 0.0676 0.0616 0.4864
注意
这是锦标赛分组的示例,显示了每对的获胜概率。