显然有：$p_i=\max\limits_{1\le j\le n}\{h_j-h_i+\sqrt{|i-j|}\}=-\min\limits_{1\le j\le n}\{-a_j-\sqrt{|i-j|}\}-h_i$

接下来就变成了，$w_{j,i}=-a_j-\sqrt{|i-j|}$ 。

不妨设 $j<i$ 这玩意儿如果要证明四边形不等式的话有：

$w_{j,i+1}+w_{j+1,i}\ge w_{j,i}+w_{j+1,i+1}$ 。

显然 $-\sqrt{i+1-j}-\sqrt{i-j-1}\ge -\sqrt{i-j}-\sqrt{i-j}$ 。推算略，很简单。

所以需要在 $j<i$ 的时候 DP 一遍，$j=i$ 特判为 $0$ ，$j>i$ 的时候把序列翻转一下跑一遍即可。

然后就是怎么跑，以 $1\le j<i$ 的这部分为例（$j>i$ 的部分反过来再跑一遍即可），$p_i=-h_i+\max\limits_{1\le j<n}w(j,i)$ ，其中 $w(j,i)=a_j+\sqrt{|i-j|}$ 。

我们可以考虑用队列记录每个决策点 $j$ 可以满足哪些区间 $[l,r]$ （其中 $j\le l\le r$），然后利用上面的公式，二分查找更新决策点能覆盖的区间即可。

const int N = 500010;
int n;
int a[N], ans[N];
long double f(int j, int i) { return a[j] + sqrtl(i - j); } // assume (1\le j < i)
struct info
{
    int opt, l, r;
    info(int _o = 0, int _l = 0, int _r = 0) : opt(_o), l(_l), r(_r) {}
};
std::deque<info> q;
void solve()
{
    q.clear(), q.push_back(info(1, 2, n));
    for (int i = 2; i <= n; ++i)
    {
        ans[i] = std::max(ans[i], (int)(ceill(f(q.front().opt, i)) - a[i]));
        if (q.size() && q.front().r == i)
            q.pop_front();
        if (q.size())
            q.front().l = i + 1;
        int pos_l = n + 1;
        while (q.size() && f(q.back().opt, q.back().l) <= f(i, q.back().l))
            pos_l = q.back().l, q.pop_back();    
        if (q.size() && f(q.back().opt, q.back().r) <= f(i, q.back().r))
        {
            int L = q.back().l, R = q.back().r;
            while (L < R)
            {
                int M = (L + R) >> 1;
                (f(q.back().opt, M) <= f(i, M)) ? (R = M) : (L = M + 1);
            }
            q.back().r = R - 1, pos_l = R;
        }
        if (pos_l <= n)
            q.push_back(info(i, pos_l, n));
    }
}
int main()
{
    n = rd();
    for (int i = 1; i <= n; ++i)
        a[i] = rd();
    solve(), std::reverse(a + 1, a + n + 1), std::reverse(ans + 1, ans + n + 1);
    solve(), std::reverse(ans + 1, ans + n + 1);
    for (int i = 1; i <= n; ++i)
        wr(ans[i]), putchar('\n');
}