假设有一个长度为 \(L\) 的木块。
定义 \(f_i\) 从 \(i\) 走到 \(L\) 的概率，有 \(f_i=\dfrac{f_{i+1}+f_{i-1}}{2}\)。由 \(f_1=0,f_L=1\) 可以递推得出 \(f_i=\dfrac{i}{L}\)。
若一个节点移动的期望收益比当前点停止的收益低，则设这个点为关键点。
从 \(i\) 出发开始移动，期望收益是其走到左右第一个关键点的概率乘上左右第一个关键点的权值，再与当前点停止的权值取 \(max\)。
设该点左右两点分别为 \(a,b\) 由之前的结论可以容易推出到 \(a\) 停止的概率为 \(\dfrac{b-i}{b-a}\)，到 \(b\) 停止的概率为 \(\dfrac{i-a}{b-a}\)。期望收益则为 \(v_a \times \dfrac{b-i}{b-a} + v_b\times \dfrac{i-a}{b-a}\)。
将每个点看作二维平面上的点 \((i,v_i)\)。将 \(a,b\) 两点连线，该一次函数与直线 \(x=i\) 的交点 \((i,t)\)，\(t\) 的值则为期望收益（式子与上面那个相同）。所以，一个为关键点，满足条件为点 \((i,v_i)\) 在点 \((i,t)\) 之上。
可以发现，这些关键点构成一个凸包。
#include <bits/stdc++.h>
using namespace std;
#define il inline
#define ptc putchar
#define pb push_back
#define R(i, l, r) for (int i = l; i <= r; ++i)
#define debug puts("--------------------------------------------")
typedef long long ll;
typedef pair<ll, ll> PII;
namespace ZeroTwo
{
template <typename T>
il void read(T &x)
{
x = 0; T f = 1; char ch;
while (!isdigit(ch = getchar())) f -= (ch == '-') << 1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch & 15), ch = getchar();
x *= f;
}
template <typename T, typename ...L>
il void read(T &x, L &...y) {read(x); read(y...);}
template <typename T>
il void write(T x)
{
if (x < 0) ptc('-'), x = -x;
if (x > 9) write(x / 10);
ptc(x % 10 + '0');
}
template <typename T, typename ...L>
il void write(T &x, L &...y) {write(x), ptc(' '); write(y...);}
}
using namespace ZeroTwo;
#define int ll
const int P = 998244353, N = 5e5 + 5;
int n, a[N], top, p;
pair <ll, ll> sk[N * 10];
double k(PII x, PII y)
{
return (x.second - y.second) * 1.0 / (x.first - y.first);
}
void insert(PII x)
{
while (top > 1 && k(sk[top], sk[top - 1]) < k(sk[top - 1], x)) --top;
sk[++top] = x;
}
double ans[N];
signed main()
{
// freopen("walk3.in", "r", stdin);
read(n);
insert({0, 0});
R(i, 1, n)
{
read(a[i]);
insert({i, a[i]});
}
insert({n + 1, 0});
p = 0;
R(i, 1, n)
{
while (p + 1 <= top && sk[p + 1].first <= i) ++p;
// cout << p << ' ' << sk[p].first << ' ' << sk[p].second << endl;
if (sk[p].first == i) ans[i] = sk[p].second;
ans[i] = (sk[p].second * (sk[p + 1].first - i) + sk[p + 1].second * (i - sk[p].first)) * 100000.0 / (sk[p + 1].first - sk[p].first);
}
int sum = 0;
R(j, 1, n) printf("%.0f\n", floor(ans[j]));
return 0;
}