分析：
感觉很少见到这种决策单调性的题。。。
首先，转换一下题目，变为求P=max{aj+∣i?j∣}?aiP=max\{a_j+\sqrt {|i-j|}\}-a_iP=max{ aj?+∣i?j∣?}?ai?
然后就有了决策单调性：
如果在计算i时，j>k,且j优于k，那么在计算i+1时，j仍然优于k（f(x)=xf(x)=\sqrt xf(x)=x?的导函数单减）
然后就可以得到一个显然的性质：
对每个位置而言，以它为最优选择的位置一定是一个连续的区间。
然后就可以用单调队列来优化DP了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 500010
#define EPS 1e-6
using namespace std;
int n;
double a[MAXN],f[MAXN];
struct node{
int l,r,pos;node (){
}node(int l1,int r1,int pos1):l(l1),r(r1),pos(pos1) {
}
}q[MAXN];
double calc(int j,int i){
return a[j]-a[i]+sqrt(1.0*fabs(i-j));
}
int find_pos(int l,int r,int pl,int pr){
int ans=r;while(l<=r){
int mid=(l+r)>>1;if(calc(pl,mid)>calc(pr,mid))l=mid+1;else{
ans=mid;r=mid-1;}}return ans;
}
int tail,head;
void solve(){
tail=0;head=1;for(int i=1;i<=n;i++){
q[head].l++;while(head<=tail&&q[head].l>q[head].r)head++;if(head>tail||calc(i,n)>calc(q[tail].pos,n)){
while(head<=tail&&calc(q[tail].pos,q[tail].l)<calc(i,q[tail].l))tail--;if(head>tail)q[++tail]=node(i,n,i);else{
int posx=find_pos(q[tail].l,q[tail].r,q[tail].pos,i);q[tail].r=posx-1;q[++tail]=node(posx,n,i);}}f[i]=max(f[i],calc(q[head].pos,i));}
}
int main(){
SF("%d",&n);for(int i=1;i<=n;i++)SF("%lf",&a[i]);solve();reverse(a+1,a+1+n);reverse(f+1,f+1+n);solve();reverse(f+1,f+1+n);for(int i=1;i<=n;i++)PF("%d\n",int(ceil(f[i])));
}