题目描述

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

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

输入格式

第⼀⾏，两个正整数 $n,m$，分别表⽰宝⽯项链中的宝⽯的数量与种类数。

第⼆⾏，$n$ 个正整数 $t_1,t_2,...,t_n$，表⽰每枚宝⽯的种类。

输出格式

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

样例

6 2
1 2 1 2 1 2

3

7 3
3 1 3 1 2 1 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$ 中出现。