罗宾汉以劫富济贫而闻名。但这一次，他不得不采取单方面的抢劫，因为他目前所在的城市里只有富人。这座城市里总共有 $n$ 个富人，他们的房子沿着主街排成一排。住在第 $i$ 个房子里的人恰好有 $a_i$ 的钱。

罗宾汉有几名帮派成员，所以他打算提前制定抢劫计划。该计划由一个整数 $k$ 和一个实数 $t$ 描述，这意味着编号为 $k, k+1, \dots, n$ 的房子将被抢劫，并且从每间房子中恰好抢走比例为 $t$ 的钱。换句话说，计划执行后，人们剩下的钱为 $$a^{\text{new}} = [a_1, a_2, \dots, a_{k-1}, (1 - t)a_k, (1 - t)a_{k+1}, \dots, (1 - t)a_n]$$ 而抢劫的总金额将等于 $$b = t \cdot (a_k + a_{k+1} + \dots + a_n)$$

我们将抢劫后的不公平度定义为 $\max(a^{\text{new}}) - \min(a^{\text{new}})$：即抢劫后人们拥有的最大金额与最小金额之差。

罗宾汉的帮派还没有到达这座城市，所以他不知道他们能够成功抢劫多少间房子。请帮助他找出对于每个从 $1$ 到 $n$ 的 $k$，哪个 $0$ 到 $1$ 之间的 $t$ 对应于抢劫计划 $(k, t)$ 下的最小可能不公平度。如果对于固定的 $k$，最小不公平度可以通过多个不同的 $t$ 值实现，你应该选择使抢劫总金额最大的那个计划。

输入格式

第一行包含一个整数 $n$ —— 城市中居住的人数 ($1 \le n \le 2 \cdot 10^5$)。

第二行包含 $n$ 个空格分隔的整数 $a_i$ —— 每个市民拥有的初始金额 ($1 \le a_i \le 10^9$)。

输出格式

输出 $n$ 个实数 $t_i$ ($0 \le t_i \le 1$)。对于每个 $1$ 到 $n$ 之间的 $k$，二元组 $(k, t_k)$ 应表示在所有此类 $k$ 的计划中，抢劫后不公平度最小的计划；在这些计划中，应选择抢劫总金额最大的计划。

如果每个输出的数字与正确答案的绝对误差或相对误差不超过 $10^{-9}$，则你的答案被接受。

样例

样例输入 1

3
1 4 2

样例输出 1

1.00 0.75 0.50

样例输入 2

3
3 2 1

样例输出 2

1.00 0.00 0.00