시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 13 7 5 45.455%

문제

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

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

입력

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

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

출력

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

예제 입력

2 2
1 1

예제 출력

1

힌트

답이 될 수 있는 문자열은 

2 1

밖에 없다.

출처

Contest > Coder's High > Coder's High 2015 Side Contest J1번