Consider ruling out the absolute value from the sought value \(D _ i=\displaystyle\min_{j\neq i}\left\lparen\left\lvert P _ i-P _ j\right\rvert+\left\lvert i-j\right\rvert\right\rparen\).

\[\begin{aligned} D _ i&=\displaystyle\min_{j\neq i}\left\lparen\left\lvert P _ i-P _ j\right\rvert+\left\lvert i-j\right\rvert\right\rparen\\ &=\min\lbrace\min_{j\lt i}\left\lparen\left\lvert P _ i-P _ j\right\rvert+i-j\right\rparen,\min_{j\gt i}\left\lparen\left\lvert P _ i-P _ j\right\rvert+j-i\right\rparen\rbrace\\ &=\min\lbrace\min_{j\lt i,P _ j\lt P _ i}\left\lparen P _ i-P _ j+i-j\right\rparen,\min_{j\lt i,P _ j\gt P _ i}\left\lparen P _ j-P _ i+i-j\right\rparen,\min_{j\gt i,P _ j\lt P _ i}\left\lparen P _ i-P _ j+j-i\right\rparen,\min_{j\gt i,P _ j\gt P _ i}\left\lparen P _ j-P _ i+j-i\right\rparen\rbrace\\ &=\min\lbrace P _ i+i-\max_{j\lt i,P _ j\lt P _ i}\left\lparen P _ j+j\right\rparen,\min_{j\lt i,P _ j\gt P _ i}\left\lparen P _ j-j\right\rparen-\lparen P _ i-i\rparen,P _ i-i-\max_{j\gt i,P _ j\lt P _ i}\left\lparen P _ j-j\right\rparen,\min_{j\gt i,P _ j\gt P _ i}\left\lparen P _ j+j\right\rparen-\lparen P _ i+i\rparen\rbrace. \end{aligned}\]

With \(A _ i=P _ i+i\) and \(B _ i=P _ i-i\),

\[\begin{aligned} D _ i&=\min\lbrace A _ i-\max_{j\lt i,P _ j\lt P _ i}A _ j,\min_{j\gt i,P _ j\gt P _ i}A _ j-A _ i,B _ i-\max_{j\gt i,P _ j\lt P _ i}B _ j,\min_{j\lt i,P _ j\gt P _ i}B _ j-B _ i\rbrace. \end{aligned}\]

This can be solved by scanning over \(i\) while setting \(A _ i\) and \(B _ i\) to the position of \(P _ i\) on a data structure that is capable of finding the segment maximum (or minimum) like a segment tree.

A sample code follows below.

One can simplify the implementation by defining a function that handles one of the four cases and letting \(P _ i\leftarrow N+1-P_i\) to cover all the four.

#include <iostream>
#include <vector>
#include <atcoder/segtree>

using namespace std;

constexpr int INF = 100000000;

// Prepare a segment tree for segment max
using S = int;
int op(int a, int b) { return max(a, b); }
int e() { return -INF; }
using segtree = atcoder::segtree<S, op, e>;

void calc(const int N, const vector<int> &P, vector<int> &D) {
    // chmin(D[i], P[i] + i - max_{j < i && P[j] < P[i]} {P[j] + j}
    segtree segment_tree(N);
    for (int i = 0; i < N; ++i) {
        D[i] = min(D[i], P[i] + i - segment_tree.prod(0, P[i]));
        segment_tree.set(P[i] - 1, P[i] + i);
    }
}

int main() {

    int N;
    cin >> N;
    vector<int> P(N);
    for (auto &&p : P) cin >> p;
    vector<int> D(N, INF);

    // Handle j such that j < i and P[j] < P[i]
    calc(N, P, D);

    // j < i and P[j] > P[i]
    for (auto &&p : P) p = N + 1 - p;
    calc(N, P, D);

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

    // j > i and P[j] < P[i]
    for (auto &&p : P) p = N + 1 - p;
    calc(N, P, D);

    // reverse again and print
    reverse(begin(P), end(P));
    reverse(begin(D), end(D));
    for (int i = 0; i < N; ++i) cout << D[i] << " ";
    cout << endl;

    return 0;
}