#include
using namespace std;
const int maxn = 500009;
int n, a[maxn], z[maxn], ans, sa[maxn], sr[maxn]; double sqa[maxn];
void pre(int n) { for (int i = 0, j = 0; j <= n; ++ i) for (; j <= i * i && j <= n; ++ j) z[j] = i; for (int i = 0; i <= n; ++ i) sqa[i] = sqrt(i); }
inline double fi(int j, int i) { return a[j] + sqa[i - j]; } inline int fii(int j, int i) { return a[j] + z[i - j]; }
void calc(int* ans) { static int q[maxn], dv[maxn]; int hd(0), tl(0); for (int i = 0; i < n; ++ i) { while (hd < tl && dv[hd + 1] <= i) ++ hd; if (hd < tl && dv[hd] < i) dv[hd] = i; if (hd >= tl || fi(q[tl - 1], n) < fi(i, n)) { while (hd < tl && fi(q[tl - 1], dv[tl - 1]) <= fi(i, dv[tl - 1])) – tl; if (hd < tl) { int l(dv[tl - 1]), r(n); dv[tl] = r; while (l < r) { int md((l + r) » 1); if (fi(i, md) >= fi(q[tl - 1], md)) { dv[tl] = md; r = md - 1; } else l = md + 1; } } else dv[tl] = i; q[tl ++] = i; dv[tl] = n; } ans[i] = fii(q[hd], i); } }
int main() { #ifndef ONLINE_JUDGE freopen(".in", “r”, stdin); #endif
scanf("%d", &n);
pre(n);
for (int i = 0; i < n; ++ i)
scanf("%d", a + i);
calc(sa);
for (int i = 0; i < n - i - 1; ++ i)
swap(a[i], a[n - i - 1]);
calc(sr);
for (int i = 0; i < n; ++ i) {
int y(max(sa[i], sr[n - i - 1]) - a[n - i - 1]);
printf("%d\n", max(y, 0));
}
}