宝石项链

题目描述

小 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

16 221 2 1 2 1 2

输出样例 1

13

输入样例 2

17 323 1 3 1 2 1 2

输出样例 2

12

数据范围

对于 $40$ 的测试点，保证 $2\le n\le 1000$。

对于所有测试点，保证 $2\le n\le 10^{5}$，$2\le m\le n$，$1\le t_{i}\le m$，保证 $1,2,...,m$ 均在 $t_{1},t_{2},...,t_{n}$ 中出现。