主观难度：【2】
毕竟是才学的东西，挺合理的。
题目要我们对 \(\forall i \in [1, n]\) 求 \(\max_{ 1 \le j \le n}\{ \lceil a_j + \sqrt{|i-j|} \rceil \}\)。
这个 ceil 我们可以暂时不管它。看着绝对值我们感觉不太舒服，于是我们正着做一遍再倒着做一遍，两遍取 max。式子变成了 \(ans_i = \max_{1 \le j \le i}\{ a_j + \sqrt{i-j} \}\)
我们可以感性地理解这个东西的决策单调性。可以在大脑中想象一堆从点 \((i, y_i)\) 出发的解析式为 \(y = \sqrt{x}\) 的函数，然后将它们整合为一个类似于上凸壳的东西。我们发现凸壳中相邻两边的起点的横坐标总是递增的，所以具有决策单调性。
然后随便用一种决策单调性的优化搞搞即可。
#include <bits/stdc++.h>
#define llong long long
#define N 500005
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}int n;
int a[N];
double dp[N], sq[N];#define mid ((l+r)>>1)
inline void solve(int l, int r, int L, int R){double maxn = 0; int pos = 0;for(int i = L; i <= min(mid, R); ++i)if(a[i]+sq[mid-i] > maxn) maxn = a[i]+sq[mid-i], pos = i;dp[mid] = max(dp[mid], maxn);if(l != r) solve(l, mid, L, pos), solve(mid+1, r, pos, R);return;
}int main(){freopen("in.txt", "r", stdin);read(n);for(int i = 1; i <= n; ++i) read(a[i]);for(int i = 1; i <= n; ++i) sq[i] = sqrt(i);solve(1, n, 1, n);reverse(a+1, a+n+1), reverse(dp+1, dp+n+1);solve(1, n, 1, n);reverse(a+1, a+n+1), reverse(dp+1, dp+n+1);for(int i = 1; i <= n; ++i) printf("%d\n", (int)ceil(dp[i])-a[i]);return 0;
}