D - Permutation Subsequence Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 425 点

問題文

(1,2,\dots,N) を並び替えて得られる数列 P=(P_1,P_2,\dots,P_N) が与えられます。

長さ K の正整数列 (i_1,i_2,\dots,i_K) であって、以下の条件を共に満たすものを良い添字列と呼びます。

  • 1\leq i_1 < i_2 < \dots < i_K \leq N
  • (P_{i_1},P_{i_2},\dots,P_{i_K}) はある連続する K 個の整数を並び替えることで得られる。
    厳密には、ある整数 a が存在して、\lbrace P_{i_1},P_{i_2},\dots,P_{i_K} \rbrace = \lbrace a,a+1,\dots,a+K-1 \rbrace。

全ての良い添字列における i_K-i_1 の最小値を求めてください。 なお、本問題の制約下では良い添字列が必ず 1 つ以上存在することが示せます。

制約

  • 1\leq K \leq N \leq 2\times 10^5
  • 1\leq P_i\leq N
  • i\neq j ならば P_i\neq P_j
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N K
P_1 P_2 \dots P_N

出力

全ての良い添字列における i_K-i_1 の最小値を出力せよ。

入力例 1

4 2
2 3 1 4

出力例 1

1

良い添字列は (1,2),(1,3),(2,4) の 3 つです。 例えば (i_1,i_2)=(1,3) は、 1\leq i_1 < i_2 \leq N かつ (P_{i_1},P_{i_2})=(2,1) が連続する 2 つの整数 1,2 の並び替えなので良い添字列です。

これらの良い添字列のうち i_K-i_1 の値が最小となるのは (1,2) で、そのときの値は 2-1=1 です。

入力例 2

4 1
2 3 1 4

出力例 2

0

どの良い添字列においても i_K-i_1=i_1-i_1=0 です。

入力例 3

10 5
10 1 6 8 7 2 5 9 3 4

出力例 3

5

Score: 425 points

Problem Statement

You are given a permutation P = (P_1, P_2, \dots, P_N) of (1, 2, \dots, N).

A length-K sequence of indices (i_1, i_2, \dots, i_K) is called a good index sequence if it satisfies both of the following conditions:

  • 1 \leq i_1 < i_2 < \dots < i_K \leq N.
  • The subsequence (P_{i_1}, P_{i_2}, \dots, P_{i_K}) can be obtained by rearranging some consecutive K integers.
    Formally, there exists an integer a such that \lbrace P_{i_1},P_{i_2},\dots,P_{i_K} \rbrace = \lbrace a,a+1,\dots,a+K-1 \rbrace.

Find the minimum value of i_K - i_1 among all good index sequences. It can be shown that at least one good index sequence exists under the constraints of this problem.

Constraints

  • 1 \leq K \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq N
  • P_i \neq P_j if i \neq j.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
P_1 P_2 \dots P_N

Output

Print the minimum value of i_K - i_1 among all good index sequences.

Sample Input 1

4 2
2 3 1 4

Sample Output 1

1

The good index sequences are (1,2),(1,3),(2,4). For example, (i_1, i_2) = (1,3) is a good index sequence because 1 \leq i_1 < i_2 \leq N and (P_{i_1}, P_{i_2}) = (2,1) is a rearrangement of two consecutive integers 1, 2.

Among these good index sequences, the smallest value of i_K - i_1 is for (1,2), which is 2-1=1.

Sample Input 2

4 1
2 3 1 4

Sample Output 2

0

i_K - i_1 = i_1 - i_1 = 0 in all good index sequences.

Sample Input 3

10 5
10 1 6 8 7 2 5 9 3 4

Sample Output 3

5