战前准备
题号：NC296761
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

这边奥比土帮小 Z 做手术，另一边五大忍村开始组织应对第四次忍界大战。
在战前演讲中，他们发现排兵布阵有一个问题。
形式化地，对于长度为 n 的数组 a，满足 a_i \in [0, m) 且 0 \sim m - 1 的每个数都在 a 中出现过。

现在旮旯要对这 n 个数进行 k 循环移位，即令 a' = a[k \dots n] + a[1\dots (k - 1)]，其中 k \in [1, n]。
  • 例如 a = [0, 1, 2, 3]，那么 k = 3 时得到的 a' = [2, 3, 0, 1]。
对于当前循环移位得到的数组 a'，设 v \in [0, m) 的首次出现下标为 p(v)，我们称 a' 为好数组当且仅当 a' 满足：
  • 对 \forall v \in [0, m - 1) 都要有 p(v) < p(v + 1)。
现在旮旯正在演讲，不能分心计算，所以他想请你帮他计算有多少个 k 循环移位好数组。

输入描述:

第 1 行两个空格隔开的正整数 n, m \ (1 \leq m \leq n \leq 2 \cdot 10^5)。
第 2 行 n 个空格隔开的正整数 a_i \ (0 \leq a_i < m)。

输出描述:

一个整数，表示 k 循环移位好数组的个数。
示例1

输入

复制 
7 4
2 1 0 3 0 1 2

输出

复制 
1

说明

k = 5 时，a' = [0, 1, 2, 2, 1, 0, 3]，可以发现只有这一个 k 循环移位好数组。
示例2

输入

复制 
5 4
0 0 1 2 3

输出

复制 
2

说明

k = 1 和 k = 2 都满足要求。
示例3

输入

复制 
4 1
0 0 0 0

输出

复制 
4

说明

整个数组只有 0，因此 4 个循环移位都满足要求。