AT_abc341_g [ABC341G] Highest Ratio

[problemUrl]: https://atcoder.jp/contests/abc341/tasks/abc341_g 長さ $ N $ の数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 $ k=1,2,\ldots,N $ について次の問題を解いてください。 - $ k\leq\ r\leq\ N $ をみたす整数 $ r $ を選んだ時、数列 $ A $ の $ k $ 項目から $ r $ 項目までの平均値としてあり得る最大値を求めよ。 ここで、数列 $ A $ の $ k $ 項目から $ r $ 項目までの平均値は $ \frac{1}{r-k+1}\displaystyle\sum_{i=k}^r\ A_i $ で定義される値である。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

$ N $ 行出力せよ。 $ i $ 行目 $ (1\leq\ i\leq\ N) $ には、$ k=i $ のときの問題の答えを出力せよ。 出力は、すべての行の出力について、その行の出力の真の値との絶対誤差または相対誤差が $ 10^{-6} $ 以下のとき正解と判定される。

### 制約 - $ 1\leq\ N\leq\ 2\times\ 10^5 $ - $ 1\leq\ A_i\leq\ 10^6 $ - 入力はすべて整数 ### Sample Explanation 1 $ k=1 $ のときについて、$ r $ としてあり得るのは $ r=1,2,3,4,5 $ であり、それぞれの時の平均値は、 - $ \frac{1}{1}=1 $ - $ \frac{1}{2}(1+1)=1 $ - $ \frac{1}{3}(1+1+4)=2 $ - $ \frac{1}{4}(1+1+4+5)=2.75 $ - $ \frac{1}{5}(1+1+4+5+3)=2.8 $ となります。よって、$ r=5 $ のときが最大であり、$ k=1 $ のときの答えは $ 2.8 $ となります。 同様に $ k=2,3,4,5 $ のときはそれぞれ $ r=4,4,4,5 $ としたときが最大であり、その値は $ \frac{10}{3}=3.333\ldots $, $ \frac{9}{2}=4.5 $, $ \frac{5}{1}=5 $, $ \frac{3}{1}=3 $ となります。