#ABC352D. 好下标序列

好下标序列

AT_abc352_d [ABC352D] Permutation Subsequence

题目描述

\hspace{15pt}给定一个由 1,2,…,n1, 2, \dots, n 组成的排列 p=(p1,p2,…,pn)p = \left(p_1, p_2, \dots, p_n\right)。长度为 nn 的排列是指由 1∼n1 \sim n 这 nn 个整数按任意顺序组成的数组,其中每个整数恰好出现一次。

\hspace{15pt}若一个长度为 kk 的正整数序列 (i1,i2,…,ik)\left(i_1, i_2, \dots, i_k\right) 同时满足以下两个条件,则称其为好下标序列:

${\hspace{20pt}}_\texttt{1.}\,1 \leqq i_1 < i_2 < \dots < i_k \leqq n$;

2. {\hspace{20pt}}_\texttt{2.}\,存在某个整数 aa,使得 $\left\{p_{i_1}, p_{i_2}, \dots, p_{i_k}\right\} = \left\{a, a+1, \dots, a+k-1\right\}$。也就是说,(pi1,pi2,…,pik)\left(p_{i_1}, p_{i_2}, \dots, p_{i_k}\right) 重新排列后,恰好是 kk 个连续整数。

\hspace{15pt}请在所有好下标序列中,求出 ik−i1i_k - i_1 的最小值。在本题的限制下,保证至少存在一个好下标序列。

输入格式

\hspace{15pt}第一行输入两个整数 $n, k \left(1 \leqq k \leqq n \leqq 2 \times 10^5\right)$ 代表排列的长度和好下标序列的长度。

\hspace{15pt}第二行输入 nn 个整数 $p_1, p_2, \dots, p_n \left(1 \leqq p_i \leqq n\right)$ 代表这个排列。保证 pp 中每个整数恰好出现一次。

输出格式

\hspace{15pt}在一行上输出一个整数,代表所有好下标序列中 ik−i1i_k - i_1 的最小值。

测试样例

4 2
2 3 1 4
1

样例 1 解释

\hspace{15pt}排列为 p=(2,3,1,4)p = \left(2, 3, 1, 4\right),k=2k=2,所有长度为 22 的下标序列中,好下标序列共有 33 个:

∙ (1,2)\hspace{23pt}\bullet\,\left(1, 2\right):(p1,p2)=(2,3)\left(p_1, p_2\right) = \left(2, 3\right),重排后为连续的两个整数 2,32, 3,是好的,i2−i1=1i_2-i_1=1;

∙ (1,3)\hspace{23pt}\bullet\,\left(1, 3\right):(p1,p3)=(2,1)\left(p_1, p_3\right) = \left(2, 1\right),重排后为连续的两个整数 1,21, 2,是好的,i2−i1=2i_2-i_1=2;

∙ (2,4)\hspace{23pt}\bullet\,\left(2, 4\right):(p2,p4)=(3,4)\left(p_2, p_4\right) = \left(3, 4\right),重排后为连续的两个整数 3,43, 4,是好的,i2−i1=2i_2-i_1=2。

\hspace{15pt}其余下标序列,例如 (1,4)\left(1, 4\right) 对应 (2,4)\left(2, 4\right),(3,4)\left(3, 4\right) 对应 (1,4)\left(1, 4\right),都不是连续的两个整数。因此最小值为 11。

4 1
2 3 1 4
0

样例 2 解释

\hspace{15pt}此时 k=1k=1,任意单个下标都能构成好下标序列。由于 iki_k 与 i1i_1 是同一个下标,ik−i1=i1−i1=0i_k-i_1=i_1-i_1=0,因此答案为 00。

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