宝石项链：计算满足条件的最多划分段数

时间限制：1.0 s
内存限制：512.0 MB

题目描述

小A有一串包含 n 枚宝石的宝石项链，这些宝石按照在项链中的顺序依次以 1,2...,n 编号，第 n 枚宝石与第 1 枚宝石相邻。项链由 m 种宝石组成，其中第 i 枚宝石种类为 $t_i$。

小A想将宝石项链分给他的好朋友们。具体而言，小A会将项链划分为若干连续段，并且需要保证每段都包含全部 m 种宝石。请帮小A计算在满足条件的前提下，宝石项链最多可以划分为多少段。

输入格式

第一行，两个正整数 n，m 分别表示宝石项链中的宝石的数量与种类数。
第二行，n 个正整数 $t_1,t_2,...t_n$，表示每枚宝石的种类。

输出格式

输出一行，一个整数，表示宝石项链最多可以划分的段数。

样例

输入样例 1

6 2
1 2 1 2 1 2

输出样例 1

3

输入样例 2

7 3
3 1 3 1 2 1 2

输出样例 2

2

数据范围

对于 40% 的测试点，保证 $2 \leq n \leq 1000$。
对于所有测试点，保证 $2 \leq n \leq 10^5$，$2 \leq m \leq n$，$1 \leq t_i \leq m$，保证 $1,2,...,m$ 均在 $t_1, t_2, ..., t_n$ 中出现。