各 \(i=1,2,\ldots,N-K+1\) に対して以下の値を求め，それの最小値が答えになります．

• \(j=i,i+1,\ldots,i+K-1\) の中で \(P\) の中で最も右に登場するものの添え字を \(idx_R\)，最も左に登場するものの添え字を \(idx_L\) としたとき，\(idx_R-idx_L\)

順列 \(Q\) を \(P\) の逆順列（各 \(i\) に対して \(P_{Q_i}=i\) が成り立つ）とすると，\(idx_R,idx_L\) はそれぞれ \(\underset{i\leq j\leq i+K-1}{\max}Q_j, \underset{i\leq j\leq i+K-1}{\min}Q_j\) になります．スライド最小値というアルゴリズムを用いると，すべての \(i\) に対する \(\underset{i\leq j\leq i+K-1}{\max}Q_j\) や \(\underset{i\leq j\leq i+K-1}{\min}Q_j\) を \(O(N)\) で求めることができます．

実装例 (Python)