时间限制: 2秒 / 内存限制: 1024MB

得分: 425分

---

问题描述

给定一个排列 P = (P₁, P₂, ..., PN)，这是一个 1 到 N 的排列。

一个长度为 K 的索引序列 (i₁, i₂, ..., iK) 被称为 ​好索引序列​，如果它满足以下两个条件：

1. 1 ≤ i₁ < i₂ < ... < iK ≤ N。
2. 子序列 (Pᵢ₁, Pᵢ₂, ..., PᵢK) 可以通过重新排列一些连续的 K 个整数得到。更正式地说，存在一个整数 a，使得 {Pᵢ₁, Pᵢ₂, ..., PᵢK} = {a, a+1, ..., a+K-1}。

要求你找到所有好索引序列中，iK - i₁ 的最小值。

可以证明，在本题的约束条件下，至少存在一个好索引序列。

---

输入

输入从标准输入给出，格式如下：

N K
P₁ P₂ ... PN

• 第一行包含两个整数 N 和 K，表示排列的长度和所求的子序列的长度。
• 第二行包含 N 个整数 P₁, P₂, ..., PN，表示排列 P。

---

输出

输出一个整数，表示所有好索引序列中 iK - i₁ 的最小值。

---

样例输入 1

4 2
2 3 1 4

样例输出 1

1

​解释​：好索引序列包括 (1, 2), (1, 3), (2, 4)。例如，(i₁, i₂) = (1, 3) 是一个好索引序列，因为 1 ≤ i₁ < i₂ ≤ N 且 (Pᵢ₁, Pᵢ₂) = (2, 1) 是连续整数 1, 2 的重新排列。

在这些好索引序列中，最小的 iK - i₁ 的值是 (1, 2)，即 2 - 1 = 1。

---

样例输入 2

4 1
2 3 1 4

样例输出 2

0

​解释​：在所有的好索引序列中，iK - i₁ = i₁ - i₁ = 0。

---

样例输入 3

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

样例输出 3

5

---

约束

• 1 ≤ K ≤ N ≤ 2 × 10⁵
• 1 ≤ Pᵢ ≤ N 且 Pᵢ ≠ Pⱼ 当 i ≠ j。
• 所有输入值均为整数。

---

题目分析

该问题要求我们找到最小的 iK - i₁，其中的 i₁, i₂, ..., iK 表示一个 "好索引序列"。要解决这个问题，我们需要：

1. ​维护一个合适的子序列​，在每次检查 Pᵢ 时，快速找出是否能形成一个符合条件的好索引序列。
2. ​找到连续的 K 个整数​，即找到一个合适的区间，使得这个区间内的值是连续的，且尽可能缩短该区间的长度。

由于数组的大小可能高达 2 × 10⁵，所以我们需要设计高效的算法来处理这个问题。