10737번 - It has the same Suffix Array

문제

길이가 \(N\)인 문자열이 있다. 이 문자열과 정확히 한 글자가 다르면서, Suffix Array가 같은 문자열의 개수는 몇 개일까?

우리가 사용할 문자의 종류는 총 \(M\)개 이므로, \(1\)에서 \(M\)까지의 자연수로 문자의 종류를 표현한다. 수가 증가하는 순서대로 사전순 순서이다.

입력

첫 번째 줄에 \(N, M (1 \leq N, M \leq 500,000)\)이 공백으로 구분되어 주어진다. \(N\)은 문자열의 길이, \(M\)은 사용하는 문자의 종류 수이다.

두 번쨰 줄에는 문자열의 각 문자를 의미하는 \(N\)개의 자연수가 순서대로 공백으로 구분되어 주어진다.

출력

입력으로 주어진 문자열과 정확히 한 글자가 다르면서, Suffix Array가 같은 문자열의 개수를 출력한다.

제한

힌트

답이 될 수 있는 문자열은

2 1

밖에 없다.