We will exhaustively enumerate the value \(a\) in the problem statement. That is, for each \(a=1,2,\dots,N-K+1\), we will try to find the following value:

• the minimum \(i_K-i_1\) when choosing \(i_1 < i_2 < \dots < i_K\) so that \(\{P_{i_1},P_{i_2},\dots,P_{i_K}\}=\{a,a+1,\dots,a+K-1\}\)

Here, let us define \(Q=(Q_1,Q_2,\dots,Q_N)\) by \(Q_j=(\) the value \(i\) such that \(P_i=j)\). When \(P\) is a permutation of \((1,2,\dots,N)\), so is \(Q\). Then, the value allow can be rephrased as follows:

• The difference between the maximum and minimum values among \(Q_a,Q_{a+1},\dots,Q_{a+K-1}\).

Let us try to evaluate this value while iterating \(a\) in ascending order. The set \(\{Q_a,Q_{a+1},\dots,Q_{a+K-1}\}\) differs only by one element (inserted and removed) as \(a\) increase by one, so the following data structure \(D\) is wanted:

• \(D\) is a data structure that manages a set and supports the following operations fast (faster than \(O(N)\)):
  • Insert one element to \(D\).
  • Remove one element from \(D\).
  • Retrieve the minimum and maximum element of \(D\).

One of the data structures that fulfill these requirements is a balanced binary search tree; std::set in C++ is one such data structure. For more details on implementation using std::set, refer to the sample code below. For implementation in other languages, please refer to reference of each language.

Sample code (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(): retrievs the maximum value
    // *st.begin(): retrievs the minimm value
    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;
}