排列子序列

题目描述

给定一个排列 $P=(P_1,P_2,\dots,P_N)$，它是$(1,2,\dots,N)$的一个排列。

长度为 $K$ 的索引序列 $(i_1,i_2,\dots,i_K)$被称为"好的索引序列"。

如果它满足以下两个条件：

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

2. 子序列 $(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$ 的最小值。在这个问题的约束条件下，可以证明至少存在一个好的索引序列。

输入格式

输入将从标准输入中以下列格式给出：

$N$ $K$

$P_1$ $P_2$ $\dots$ $P_N$

输出格式

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

输入输出样例 #1

输入 #1

4 2
2 3 1 4

输出 #1

1

输入输出样例 #2

输入 #2

4 1
2 3 1 4

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

5

说明/提示

样例 1 解释

好的索引序列有 $(1,2),(1,3)(2,4)$。例如 $(i_1,i_2)=(1,3)$ 是一个好的索引序列，因为 $1\le i_1<i_2\le 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$
• 所有输入值都是整数。