宝⽯项链

题目描述

⼩ A 有⼀串包含 枚宝⽯的宝⽯项链，这些宝⽯按照在项链中的顺序依次以 编号，第 枚宝⽯与第 枚 宝⽯相邻。项链由 种宝⽯组成，其中第 枚宝⽯种类为 。 ⼩ A 想将宝⽯项链分给他的好朋友们。具体⽽⾔，⼩ A 会将项链划分为若⼲连续段，并且需要保证每段都包含全部 种宝⽯。请帮⼩ A 计算在满⾜条件的前提下，宝⽯项链最多可以划分为多少段。

输入格式

第⼀⾏，两个正整数 ，分别表⽰宝⽯项链中的宝⽯的数量与种类数。 第⼆⾏， 个正整数 ，表⽰每枚宝⽯的种类。

输出格式

输出⼀⾏，⼀个整数，表⽰宝⽯项链最多可以划分的段数。

样例输入 #1

6 2
1 2 1 2 1 2

样例输出 #1

3

样例输入 #2

7 3
3 1 3 1 2 1 2

样例输出 #2

2

数据范围

对于 的测试点，保证 。 对于所有测试点，保证 ， ， ，保证 均在 中出现。

知识点与难度

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

测试点分布

生测试数据后，按实际 subtask 分组改写上表。