AT_abc352_d [ABC352D] Permutation Subsequence
题目描述
给定一个由 1,2,…,n 组成的排列 p=(p1,p2,…,pn)。长度为 n 的排列是指由 1∼n 这 n 个整数按任意顺序组成的数组,其中每个整数恰好出现一次。
若一个长度为 k 的正整数序列 (i1,i2,…,ik) 同时满足以下两个条件,则称其为好下标序列:
${\hspace{20pt}}_\texttt{1.}\,1 \leqq i_1 < i_2 < \dots < i_k \leqq n$;
2.存在某个整数 a,使得 $\left\{p_{i_1}, p_{i_2}, \dots, p_{i_k}\right\} = \left\{a, a+1, \dots, a+k-1\right\}$。也就是说,(pi1,pi2,…,pik) 重新排列后,恰好是 k 个连续整数。
请在所有好下标序列中,求出 ik−i1 的最小值。在本题的限制下,保证至少存在一个好下标序列。
输入格式
第一行输入两个整数 $n, k \left(1 \leqq k \leqq n \leqq 2 \times 10^5\right)$ 代表排列的长度和好下标序列的长度。
第二行输入 n 个整数 $p_1, p_2, \dots, p_n \left(1 \leqq p_i \leqq n\right)$ 代表这个排列。保证 p 中每个整数恰好出现一次。
输出格式
在一行上输出一个整数,代表所有好下标序列中 ik−i1 的最小值。
测试样例
4 2
2 3 1 4
1
样例 1 解释
排列为 p=(2,3,1,4),k=2,所有长度为 2 的下标序列中,好下标序列共有 3 个:
∙(1,2):(p1,p2)=(2,3),重排后为连续的两个整数 2,3,是好的,i2−i1=1;
∙(1,3):(p1,p3)=(2,1),重排后为连续的两个整数 1,2,是好的,i2−i1=2;
∙(2,4):(p2,p4)=(3,4),重排后为连续的两个整数 3,4,是好的,i2−i1=2。
其余下标序列,例如 (1,4) 对应 (2,4),(3,4) 对应 (1,4),都不是连续的两个整数。因此最小值为 1。
4 1
2 3 1 4
0
样例 2 解释
此时 k=1,任意单个下标都能构成好下标序列。由于 ik 与 i1 是同一个下标,ik−i1=i1−i1=0,因此答案为 0。
10 5
10 1 6 8 7 2 5 9 3 4
5