排列子序列

题目描述

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

长度为 $K$ 的下标序列 $(i_1, i_2, \dots, i_K)$ 被称为「好下标序列」,当且仅当它满足以下两个条件:

• $1 \le i_1 \lt i_2 \lt \dots \lt i_K \le 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$ 的最小值。可以证明,在本问题的约束下至少存在一个好下标序列。

输入格式

输入按以下格式从标准输入给出:

$N$ $K$
$P_1$ $P_2$ $\dots$ $P_N$

输出格式

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

样例

4 2
2 3 1 4

1

好下标序列有 $(1, 2), (1, 3), (2, 4)$。例如,$(i_1, i_2) = (1, 3)$ 是好下标序列,因为 $1 \le i_1 \lt i_2 \le N$,且 $(P_{i_1}, P_{i_2}) = (2, 1)$ 是连续两个整数 $1, 2$ 的重新排列。

在这些好下标序列中,$i_K - i_1$ 的最小值出现在 $(1, 2)$,其值为 $2 - 1 = 1$。

4 1
2 3 1 4

0

在所有好下标序列中都有 $i_K - i_1 = i_1 - i_1 = 0$。

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

5

数据范围

• $1 \le K \le N \le 2 \times 10^5$
• $1 \le P_i \le N$
• 若 $i \neq j$,则 $P_i \neq P_j$
• 输入中的所有值均为整数