You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \dots, A_N)$ 和一个正整数 $M$。
我们可以进行若干次（0次到N次）删除末尾元素的操作，使得操作后的序列不满足以下条件：

• 条件：序列中包含所有 $1$ 到 $M$ 的整数（即对于每个 $x \in \{1, 2, \dots, M\}$，序列中至少有一个元素等于 $x$）。

求满足条件的最小操作次数（即删除末尾元素的最少次数）。

输入格式

输入按以下格式给出：

N M
A_1 A_2 ... A_N  

• $N$：序列长度
• $M$：正整数
• $A_1, A_2, \dots, A_N$：整数序列，每个元素满足 $1 \le A_i \le M$

输出格式

输出一个整数，表示使条件不满足所需的最小操作次数。

输入输出样例

样例 1

输入：

5 3  
3 2 3 1 2  

输出：

2  

解释：
初始序列包含 $1, 2, 3$，满足条件。

• 删除1次末尾元素后，序列为 $(3, 2, 3, 1)$，仍包含 $1, 2, 3$，条件满足。
• 再删除1次末尾元素后，序列为 $(3, 2, 3)$，不包含 $1$，条件不满足。
  因此最小操作次数为 $2$。

样例 2

输入：

4 3  
1 3 1 3  

输出：

0  

解释：
初始序列缺少 $2$，条件不满足，无需任何操作。

限制与约定

对于 $40\%$ 的样例， $1 \le M \le N \le 100$
$1 \le A_i \le M$

对于 $100\%$ 的样例， $1 \le M \le N \le 10^6$
$1 \le A_i \le M$

保证存在至少一种操作方式使条件不满足。

• 时间限制: $1 s$
• 空间限制: $256 MB$