Let’s consider first handling the pairs \((i, j)\) where \(i > j\) and \(P_i > P_j\), and handle the rest of the cases later.

Initialize a range-max segment tree \(S\) with all elements starting at \(-\infty\). In increasing order of \(P_i\), first update \(D_i \larr \min(D_i, P_i + i - \max_{j: j < i} S_j)\). Then update \(S_i \larr P_i + i\).

Cases “\(i > j\) and \(P_i < P_j\)”, “\(i < j\) and \(P_i > P_j\)”, and “\(i < j\) and \(P_i < P_j\)” can be handled similarly. To avoid too much casework you can instead reverse and/or “flip” \(P\) (e.g. \(P_i \larr n + 1 - P_i\)), but be sure to update the correct \(D_i\).

This should solve the problem in time \(O(N \log N)\).