配列の index を \(0\) から始まるものとします。

\(A\) の並び順を反転させた数列を \(A'\) とし、更に \(B=A'_i-i\) とします。このとき、問題は次のように読み替えられます。

「\(B\) を、\(0\) 以上 \(P-(N-1)\) 以下の値のみからなる広義単調増加列にするには、最小でいくつの項の値を変更する必要があるか？」

値が \(0\) 以上 \(P-(N-1)\) 以下でない項は明らかに変更する必要があります。また、変更しない項の集合を決めた時、それらが広義単調増加列をなすならば、それ以外の項を適切に変更することで全体を広義単調増加にすることができます。逆もまた真です。

したがって、最長増加部分列(Longest Increasing Subsequence)の長さを求める問題に帰着され、セグメントツリーやBinary Indexed Tree などを用いることで \(O(N\log N)\) で問題が解けました。

通常の最長増加部分列問題と異なり、広義単調増加列を考えていることに注意してください。