[ABC352] D - Permutation Subsequence

D - Permutation Subsequence

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 425 分

题面

给定排列 ，其中 是 的一个排列。

一个索引序列 被称为一个好索引序列，如果它同时满足以下两个条件：

• 。
• 子序列 可以通过重新排列某些连续的 个整数得到。
  具体而言，存在整数 ，使得 。

找出所有好索引序列中 的最小值。可以证明，在本问题的限制条件下至少存在一个好的索引序列。

限制条件

• 若 ，则 。
• 所有输入均为整数。

---

输入

输入从标准输入中获取，格式如下：

输出

打印所有好索引序列中 的最小值。

---

输入样例 1

4 2
2 3 1 4

输出样例 1

1

好索引序列为 。例如， 是一个好的索引序列，因为 ，且 是两个连续整数 的重新排列。

在这些好索引序列中， 的最小值为 ，即 。

---

输入样例 2

4 1
2 3 1 4

输出样例 2

0

在所有好索引序列中，。

---

输入样例 3

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

输出样例 3

5