#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int nax = 500'005;
void self_max(int& me, int other) {
me = max(me, other);
}
int lg[nax];
int mx[nax][19];
int q(int l, int r) {
int L = lg[r-l+1];
return max(mx[l][L], mx[r-(1<<L)+1][L]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for(int& i : a) {
cin >> i;
}
vector<int> ans(n, 0);
lg[1] = 0;
for(int i = 2; i < n; i++) {
lg[i] = lg[i/2] + 1;
}
for(int i = 0; i < n; i++) {
mx[i][0] = a[i];
}
for(int j = 1; j < 19; j++) {
for(int i = 0; i < n; i++) {
mx[i][j] = max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
}
}
//for(int i = 0; i < n; i++) {
//for(int j = i; j < n; j++) {
//cout << i << " " << j << ": " << q(i, j) << "\n";
//}
//}
for(int i = 0; i < n; i++) {
bool in = true;
for(int p = 1; in; p++) {
in = false;
int sz = p*p;
int prev = (p-1)*(p-1);
// left interval
int l = max(0, i-sz);
int r = i - prev - 1;
if (l <= r) {
self_max(ans[i], p - a[i] + q(l, r));
in = true;
}
// right inteval
l = i + prev + 1;
r = min(n-1, i + sz);
//if (i == 0) {
//cout << l << " " << r << "\n";
//}
if (l <= r && r < n) {
self_max(ans[i], p - a[i] + q(l, r));
in = true;
}
}
}
for(int i = 0; i < n; i++) {
cout << ans[i] << "\n";
}
}
