宝石项链

题目描述

小 A 有一串包含 n 枚宝石的宝石项链，这些宝石按照在项链中的顺序依次以 1, 2, ..., n 编号，第 i 枚宝石与第 i+1 枚宝石相邻（特别地，第 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

样例解释 1

每相邻两枚宝石 1 2 都同时包含两种宝石，因此可划分成 3 段。

输入样例 2

7 3 3 1 3 1 2 1 2

输出样例 2

2

数据范围

对于所有测试点，保证 1 <= n <= 10^5，1 <= m <= n，1 <= t[i] <= m，且保证每种宝石都在序列中出现（1 到 m 均出现）。