問題文中における \(a\) の値を全探索することを考えます。 すなわち、\(a=1,2,\dots,N-K+1\) それぞれについて以下の値を求めたいです。

• \(\{P_{i_1},P_{i_2},\dots,P_{i_K}\}=\{a,a+1,\dots,a+K-1\}\) となるように \(i_1 < i_2 < \dots < i_K\) を選んだときの \(i_K-i_1\) の値

ここで、数列 \(Q=(Q_1,Q_2,\dots,Q_N)\) を、\(Q_j=(P_i=j\) を満たす \(i\) の値 \()\) と定義します。 \(P\) が \((1,2,\dots,N)\) の順列であるとき、\(Q\) もまた \((1,2,\dots,N)\) の順列です。 すると、上記の値は以下のように言い換えられます。

• \(Q_a,Q_{a+1},\dots,Q_{a+K-1}\) の最大値と最小値の差

\(a\) の昇順にこの値を求めることを考えます。集合 \(\{Q_a,Q_{a+1},\dots,Q_{a+K-1}\}\) は \(a\) を \(1\) 増やしたとき \(1\) 要素分しか変化しない（\(Q_a\) が抜けて \(Q_{a+K}\) が入る）ことから、以下のようなデータ構造 \(D\) があれば良いことがわかります。

• \(D\) は集合を管理するデータ構造であり、以下の操作を高速に（\(O(N)\) より速く）処理できる。
  • \(D\) に要素を \(1\) つ追加する。
  • \(D\) から要素を \(1\) つ削除する。
  • \(D\) に現在含まれる要素の最大値と最小値を取得する。

これらの要件を満たせるデータ構造の一つが平衡二分探索木であり、C++ の std::set などが該当します。std::set を用いた場合の実装の詳細は下記の実装例を参考にしてください。他の言語における実装については各言語のリファレンス等を参照してください。

実装例 (C++):

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> q(n);
    for (int i = 0; i < n; i++) {
        int p;
        cin >> p;
        --p;
        q[p] = i;
    }
    set<int> st;
    for (int i = 0; i < k; i++) {
        st.insert(q[i]);
    }
    // *st.rbegin() : 最大値の取得
    // *st.begin() : 最小値の取得
    int ans = *st.rbegin() - *st.begin();
    for (int i = k; i < n; i++) {
        st.erase(q[i - k]);
        st.insert(q[i]);
        ans = min(ans, *st.rbegin() - *st.begin());
    }
    cout << ans << endl;
}