← 返回题目列表

AtCoder · joi2017yo_d

D. 整理毛绒动物(毛绒玩具)

中文机器翻译题面 查看原题

配点: 100 点

問題

一名 JOI 人员在玩具店工作。今天我决定在店里整理一下毛绒动物角。

在毛绒动物角的架子上,N 毛绒动物从左到右排列成一排。架子由隔板隔开。 它分为 N 部分,1 在一个隔间中 放置 1 毛绒动物。这家玩具店共有 M 我们出售不同种类的毛绒动物,每种 它们的编号最大为 1 减去 M 。排列在架子上 每个 N 毛绒动物都是 M 是以下类型之一。此外,每种毛绒玩具至少 有 1 件。

为了改善外观,我想重新排列毛绒玩具,以便所有相同类型的毛绒动物连续放置在架子上。我决定使用以下方法重新排列毛绒动物。 选择一些

  • N 毛绒动物并将它们从架子上拿出来。没有取出的毛绒玩具的位置不会移动。
  • 按照您喜欢的顺序将取出的毛绒动物放回架子的空部分。

分类后,所有相同类型的毛绒动物必须连续放置在货架上。编写一个程序来找出要排序的毛绒动物的最小数量。 由


入力

输入是 1 + N 行组成。

1 在线 2 整数 给出了 N, M (1 \leqq N \leqq 100\,000,1 \leqq M \leqq 20) 以空格作为分隔符,毛绒玩具为 有 N 类型。 M 表示有不同类型。

继续 N 每行包含1 以上 M 写入以下整数。N 行中的 i 行目 (1 \leqq i \leqq N中写入的整数来自架子的左侧。 代表放置在第 i 个隔间中的毛绒动物的类型。对于每种类型,至少 保证 1 毛绒动物存在。

出力

设置要排序的毛绒动物的最小数量。 在 1 行。


入力例 1

7 2
1
2
2
2
1
2
1

出力例 1

2

入力例 1 中,首先放置的毛绒玩具的类型是从左到右。 1, 2, 2, 2, 1, 2, 1 。为了尽量减少取出进行分类的毛绒动物的数量,从左侧开始 1 th 和 从左边开始取出第 6 个毛绒动物。 1 第类型 2 毛绒动物从左边开始 只需放置 6 第类型 1 毛绒动物即可。此时要取出的毛绒玩具数量为 2 。


入力例 2

12 4
1
3
2
4
2
1
2
3
1
1
3
4

出力例 2

7