描述

Farmer John 的 N 头奶牛（1 ≤ N ≤ 100,000）排成一排。每头奶牛的品种用一个范围在 1 到 K（1 ≤ K ≤ 10,000）之间的数字表示。例如，一行 14 头奶牛的品种可能是这样的：

1 5 3 2 5 1 3 4 4 2 5 1 2 3

Farmer John 的敏锐数学头脑注意到了像上面这样的数字序列的许多性质。例如，他注意到序列 3 4 1 3 是上述品种 ID 序列的一个子序列（不一定是连续的）。FJ 很好奇，他能否用 1 到 K 范围内的数字构造一个尽可能短的序列，而这个序列不是奶牛品种 ID 序列的子序列。请帮助他解决这个问题。

输入格式

• 第 1 行：两个整数 N 和 K。
• 第 2 到 N+1 行：每行包含一个整数，表示一头奶牛的品种 ID。第 2 行描述第 1 头奶牛；第 3 行描述第 2 头奶牛；依此类推。

输出格式

• 第 1 行：最短的、不是输入序列子序列的序列的长度。

输入示例 1

14 5
1
5
3
2
5
1
3
4
4
2
5
1
2
3

输出示例 1

3

提示

• 所有长度为 1 的序列都出现了。
• 每个长度为 2 的序列（共 25 个）也都出现了。
• 在长度为 3 的序列中，序列 2, 2, 4 没有出现。

来源

USACO 2004 US公开赛