分数: 425 点
问题陈述
给你一个排列 P = (P_1, P_2, \dots, P_N) of (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 在所有好的索引序列中。可以证明,在该问题的约束下,至少存在一个好的索引序列。
约束
- 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.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K P_1 P_2 \dots P_N
输出
打印最小值 i_K - i_1 在所有好的索引序列中。
示例输入 1
4 2 2 3 1 4
示例输出 1
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
4 1 2 3 1 4
示例输出 2
0
i_K - i_1 = i_1 - i_1 = 0 在所有好的索引序列中。
示例输入 3
10 5 10 1 6 8 7 2 5 9 3 4
示例输出 3
5