AT_abc352_d [ABC352D] Permutation Subsequence

题目描述

给定一个由 $1,2,\dots,N$ 组成的排列 $P=(P_1,P_2,\dots,P_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$ 的最小值。

输入输出样例 #1

输入 #1

4 2
2 3 1 4

输出 #1

1

输入输出样例 #2

输入 #2

4 1
2 3 1 4

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

5

说明/提示

限制条件

• $1\leq K \leq N \leq 2\times 10^5$
• $1\leq P_i \leq N$
• 如果 $i\neq j$，则 $P_i\neq P_j$
• 输入均为整数

样例解释 1

好下标序列有 $(1,2),(1,3),(2,4)$ 共 $3$ 个。例如 $(i_1,i_2)=(1,3)$，满足 $1\leq i_1 < i_2 \leq N$，且 $(P_{i_1},P_{i_2})=(2,1)$ 是连续的 $2$ 个整数 $1,2$ 的一种排列，因此是好下标序列。在这些好下标序列中，$i_K-i_1$ 的最小值为 $(1,2)$，此时 $2-1=1$。

样例解释 2

对于任意好下标序列，$i_K-i_1=i_1-i_1=0$。

由 ChatGPT 4.1 翻译