战前准备
题号: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)
2n 个空格隔开的正整数 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 = 1k = 2 都满足要求。
示例3

输入

复制
4 1
0 0 0 0

输出

复制
4

说明

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