Time Limit: 2 sec / Memory Limit: 1024 MB

问题陈述

给你一个 $(1, 2, \dots, N)$ 的排列组合 $P = (P_1, P_2, \dots, P_N)$ 。

如果一个长度为 $K$ 的索引序列 $(i_1, i_2, \dots, i_K)$ 同时满足以下两个条件，那么这个索引序列被称为好索引序列：

• 子序列 $(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 \leq K \leq N \leq 2 \times 10^5$
• $1 \leq P_i \leq N$
• $P_i \neq P_j$ 如果 $i \neq j$ .
• 所有输入值均为整数。

输入

输入内容由标准输入法提供，格式如下

N K
$P_1 \ P_2 ... P_N$

输出

打印所有良好索引序列中 $i_K - i_1$ 的最小值。

Sample Input 1

4 2
2 3 1 4

样本输出 1

1

好的索引序列是 $(1,2),(1,3),(2,4)$ 。例如， $(i_1, i_2) = (1,3)$ 是一个好的索引序列，因为 $1 \leq i_1 < i_2 \leq N$ 和 $(P_{i_1}, P_{i_2}) = (2,1)$ 是两个连续整数 $1, 2$ 的重排。

在这些良好的索引序列中， $i_K - i_1$ 的最小值为 $(1,2)$ ，即 $2-1=1$ 。

Sample Input 2

4 1
2 3 1 4

输出示例 2

0

$i_K - i_1 = i_1 - i_1 = 0$ 在所有好的索引序列中。

Sample Input 3

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

Sample Output 3

5