この問題は、\(P\) が順列でなくても高速に解くことができます。

公式解説で述べたように、\(\displaystyle D ^ \prime _ i=P _ i+i-\max_{j\lt i,P _ j\lt P _ i}(P _ j+j)\) が計算できれば十分です。

\(i\) まで見たときに、これから \(j\) として選ばれうる値のみ保持しておくことを考えます。

整数 \(j\) に対して、\(P _ j\gt P _ k\) かつ \(P _ j+j\lt P _ k+k\) となるような \(k\) が存在するならそのような \(j\) が最大を与えることはありません。 逆に、そうでないようなすべての \(j\) は適当な \((i,P _ i)\) の組で選ばれる可能性があります。

よって、保持するべき \((P _ i,P _ i+i)\) の組を辞書順で昇順に並べると、\(P _ i+i\) も昇順に並んでいます。 そのような列を管理できたら、その上で二分探索を行うことで \(D ^ \prime _ i\) を高速に求めることができます。

\((P _ i,P _ i+i)\) を昇順に並べた列は、この記事 にあるようなテクニックを用いることで全体で \(O(N\log N)\) 時間で管理することができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <limits>
#include <set>
#include <utility>
#include <algorithm>

int main() {
    using namespace std;

    unsigned long N;
    cin >> N;
    vector<unsigned long> P(N);
    for(auto&& p : P)cin >> p;
    vector<unsigned long> D(N, numeric_limits<unsigned long>::max());

    const auto calc{[&P, &N, &D]{
        // chmin(D[i], min_{j < i && P[j] < P[i]} (P[i] + i) - (P[j] + j)); (i = 1, 2, ..., N)
        // を O(N log N) 時間で実行

        // 最小値を与える可能性がある j を P[j] の昇順に管理
        set<pair<unsigned long, unsigned long>> cost_set;

        for(unsigned long i{}; i < N; ++i){
            const auto value{P[i]};
            const auto cost{P[i] + i};

            // D[i] を更新
            auto it{cost_set.upper_bound({P[i], 0})};
            if(it != begin(cost_set))D[i] = min(D[i], cost - prev(it) -> second);

            // j の候補を更新
            while(it != end(cost_set) && it -> second <= cost)it = cost_set.erase(it);
            cost_set.emplace_hint(it, value, cost);
        }
    }};

    // j < i かつ P[j] < P[i] なる j について計算
    calc();

    // j < i かつ P[j] > P[i]
    for(auto&& p : P)p = N - p;
    calc();

    // j > i かつ P[j] > P[i]
    reverse(begin(P), end(P));
    reverse(begin(D), end(D));
    calc();

    // j > i かつ P[j] < P[i]
    for(auto&& p : P)p = N - p;
    calc();

    // 反転しているので逆順に出力
    for(unsigned long i{N}; i--; )cout << D[i] << (i ? ' ' : '\n');

    return 0;
}