Permutation Subsequence

题目描述

你被给定了一个排列 $P = (P_1, P_2, \dots, P_N)$，它是 $(1, 2, \dots, 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$ 的最小值。可以证明在本题约束下至少存在一个良好下标序列。

输入格式

输入从标准输入给出，格式如下： $N$ $K$ $P_1$ $P_2$ $\dots$ $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 \leq K \leq N \leq 2 \times 10^5$ $1 \leq P_i \leq N$ $P_i \neq P_j$ if $i \neq j$. 所有输入值均为整数。良好下标序列为 $(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$。
$i_K - i_1 = i_1 - i_1 = 0$ 在所有良好下标序列中均成立。

标签: AtCoder|abc352D

来源

AtCoder|abc352D