← 返回题目列表

AtCoder · abc352_d

G. 排列子序列

中文机器翻译题面 查看原题

分数: 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