P83051

邦邦的大合唱站队

难度 7 级 初三 动态规划入门 状态压缩
讨论 统计 4通过 16提交 25%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

BanG Dream!里的所有偶像乐队要一起大合唱,不过在排队上出了一些问题。

N个偶像排成一列,他们来自M个不同的乐队。每个团队至少有一个偶像。

现在要求重新安排队列,使来自同一乐队的偶像连续的站在一起。重新安排的办法是,让若干偶像出列(剩下的偶像不动),然后让出列的偶像一个个归队到原来的空位,归队的位置任意。

请问最少让多少偶像出列?

输入

第一行2个整数N,M。

接下来N个行,每行一个整数a_i(1\le a_i \le M),表示队列中第i个偶像的团队编号。

输出

一个整数,最少让多少偶像出列的数量

样例

样例 1
输入
12 4
1
3
2
4
2
1
2
3
1
1
3
4
输出
7

提示

样例解释:打勾处为需要换位置的偶像,右侧这一列为最终交换位置后的队列的顺序

1 3 √

3 3

2 3 √

4 4

2 4 √

1 2 √

2 2

3 2 √

1 1

1 1

3 1 √

4 1 √

对于全部数据,1\le N\le 10^5, M\le 20

来源

用户上传

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交