反子序列(Anti-Subsequence)

题目描述

给定一个长度为 $n$ 的数列：$a_1, a_2, \cdots, a_n$，且每个元素都满足 $1 \leq a_i \leq k$。请找出一个数列，它的每个元素同样不超过 $k$ 且不低于 $1$，且新数列不是原数列的子序列（所谓子序列，就是原序列中部分元素构成的序列，这些元素在原序列中不必连续）。请输出新序列的最短长度。

输入格式

第一行：两个整数 $n$ 与 $k$； 第二行：$n$ 个整数表示 $a_1, a_2, \cdots, a_n$。

输出格式

单个正整数：表示所求数列的最短长度。

样例输入 #1

5 2
2 2 1 1 2

样例输出 #1

3

说明：1,1,1 是最短的满足条件的序列之一，长度为3

样例输入 #2

9 3
1 2 3 1 2 3 1 2 3

样例输出 #2

4

数据范围

• 对于 50% 数据，$1 \leq n \leq 100$，$1 \leq k \leq 10$；
• 对于 100% 数据，$1 \leq n \leq 100,000$，$1 \leq k \leq 10000$。

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐。

测试点分布