#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define maxc 1000000007
#define N 500005
using namespace std;
struct Dequeue
{
int a[N*2];
int top, bot;
void clear() {top = 1; bot = 0;}
void push_back(int x) {a[++bot] = x;}
void pop_back() {bot--;}
void pop_front() {top++;}
int back() {return a[bot];}
int front() {return a[top];}
bool empty() {return (bot < top);}
}q;
int n, a[N], x2[N], res[N], delta[N];
void inline MAX(int &A, int B) {A = max(A, B);}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("INP.TXT", "r", stdin);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= sqrt(n) + 1; i++)
x2[i] = i*i;
for (int i = 1; i <= sqrt(n) + 1; i++)
delta[i] = x2[i] - x2[i-1];
for (int can = 1; can <= sqrt(n)+1; can++)
{
int len = delta[can];
q.clear();
for (int i = 1; i <= n; i++)
{
int pos = i - x2[can-1] - 1;
while (!q.empty() && q.front() <= pos - len)
q.pop_front();
if (pos > 0)
{
while (!q.empty() && a[q.back()] <= a[pos])
q.pop_back();
q.push_back(pos);
}
if (!q.empty()) MAX(res[i], a[q.front()] + can);
}
q.clear();
for (int i = n; i >= 1; i--)
{
int pos = i + x2[can-1] + 1;
while (!q.empty() && q.front() >= pos + len)
q.pop_front();
if (pos <= n)
{
while (!q.empty() && a[q.back()] <= a[pos])
q.pop_back();
q.push_back(pos);
}
if (!q.empty()) MAX(res[i], a[q.front()] + can);
}
}
for (int i = 1; i <= n; i++)
if (res[i] <= a[i]) cout <<0<<'\n';
else cout <<res[i] - a[i]<<'\n';
}
