题目描述

给定一个排列 $P = (P_1, P_2, \cdots, P_N)$，它是 $(1, 2, \cdots, N)$ 的一个排列。
长度为 $K$ 的索引序列 $(i_1, i_2, \cdots, i_K)$ 被称为"好的索引序列"，如果它满足以下两个条件：

1. $1 \leq i_1 < i_2 < \cdots < i_K \leq N$。

2. 子序列 $(P_{i_1}, P_{i_2}, \cdots, P_{i_K})$ 可以通过重新排列某些连续的 $K$ 个整数得到。形式上，存在一个整数 $a$ 使得 ${P_{i_1},P_{i_2},\cdots,P_{i_K}} = {a,a+1,\cdots,a+K-1}$。

在所有好的索引序列中，找出 $i_K - i_1$ 的最小值。在这个问题的约束条件下，可以证明至少存在一个好的索引序列。

输入格式

输入将从标准输入中以下列格式给出：
$N$ $K$
$P_1$ $P_2$ $\cdots$ $P_N$

输出格式

输出所有好的索引序列中 $i_K - i_1$ 的最小值。

样例

4 2
2 3 1 4

1

4 1
2 3 1 4

0

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

5

样例解释

【样例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$。

【样例2说明】
在所有好的索引序列中，$i_K - i_1 = i_1 - i_1 = 0$。

数据范围

$1 \leq K \leq N \leq 2 \times 10^5$
$1 \leq P_i \leq N$
如果 $i \neq j$，则$P_i \neq P_j$
所有输入值都是整数。

来源

• AtCoder ABC352D