4219: Permutation Subsequence

# Permutation Subsequence ### 内存 1024MB ### 时间 2S ## 题目描述 给定一个排列 $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$ 的最小值。 ## 输入输出样例 ### 输入样例1 ``` 4 2 2 3 1 4 ``` ### 输出样例1 ``` 1 ``` ### 输入样例2 ``` 4 1 2 3 1 4 ``` ### 输出样例2 ``` 0 ``` ### 输入样例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 \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$ 所有输入值都是整数。 ## 题目来源 ABC352D