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

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

第一行：两个正整数 n, m ，分别表示宝石项链中的宝石数量与种类数。

第二行： n 个正整数 t_1, t_2, \ldots, t_n ，表示每枚宝石的种类。

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

数据范围

• 对于 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, \ldots, m 均在 t_1, t_2, \ldots, t_n 中出现。

GESP25年12月八级

GESP八级25年12月倍增