휴대폰 벨소리

모비드와 모드레드는 누구 휴대폰 벨소리가 더 인상적인지를 두고 겨룬다. 처음에는 유명한 데스메탈 리프로 시작했지만, 요즘 모드레드는 훨씬 추상적인 쪽으로 갔다. 그의 휴대폰은 쓸 수 있는 모든 소리의 순열을 전부 이어 붙인 수열을 울린다. 모비드는 이걸 이길 방법을 한참 찾다가 마침내 답을 찾았다.

모비드는 자기 벨소리에서 이웃한 두 조각이 정확히 같은 소리로 이루어지는 일이 절대 없게 만들기로 했다 (같은 소리가 여러 번 나오는 것까지 세어서). 이런 벨소리를 좋은 벨소리라고 부른다. 정확히 말하면, 벨소리 $a = a_1, \dots, a_k$가 좋은 벨소리라는 것은 $1 \le i$이고 $i + 2j - 1 \le k$인 모든 $i$, $j$에 대해 두 조각 $a_i, \dots, a_{i+j-1}$과 $a_{i+j}, \dots, a_{i+2j-1}$이 정확히 같은 소리로 이루어지지 않는다는 뜻이다. 즉 어떤 소리 하나는 두 조각에서 등장 횟수가 서로 다르다.

모비드가 원하는 벨소리는 조건 세 가지를 모두 만족한다.

1. 좋은 벨소리이다.
2. 쓸 수 있는 소리 $n$가지를 모두 한 번 이상 쓴다.
3. 더 길게 만들 수 없다. 어떤 소리를 맨 앞에 붙이든 맨 뒤에 붙이든 좋은 벨소리가 되지 않는다. 늘릴 수 있는데 모드레드가 그 확장을 자기 벨소리로 쓴다면, 상상하기도 싫은 굴욕이다.

세 번째 조건은 소리를 하나만 붙여 보면 판정된다. 한쪽에 소리 하나도 붙일 수 없으면 더 긴 것도 붙일 수 없다.

벨소리 하나가 주어진다. 이 벨소리가 세 조건을 모두 만족하는지 판정하는 프로그램을 작성하시오.

첫째 줄에 정수 $n$과 $k$가 공백으로 구분되어 주어진다. $n$은 쓸 수 있는 서로 다른 소리의 개수이고 ($1 \le n \le 50000$), $k$는 벨소리의 길이이다 ($1 \le k \le 2000$). 소리에는 $0$부터 $n-1$까지 번호가 붙어 있다.

둘째 줄에 벨소리를 이루는 정수 $a_1, a_2, \dots, a_k$가 공백 하나로 구분되어 주어진다 ($0 \le a_i \le n-1$).

주어진 벨소리가 세 조건을 모두 만족하면 첫째 줄에 YES를, 하나라도 어기면 NO를 출력한다.

$i$와 $j$를 모두 훑으면서 두 조각을 그대로 비교하면 $O(k^3)$이 걸린다. 자르는 위치를 고정하고 양쪽 조각을 한 칸씩 같이 키우면서 두 다중집합의 차이만 갱신하면 좋은 벨소리인지를 $O(k^2)$에 판정할 수 있다. 앞이나 뒤에 소리 하나를 붙이는 경우도 같은 방법으로 각각 $O(k)$에 처리된다. 붙였을 때 좋은 벨소리가 깨지는 소리를 모두 모은 다음, 그 집합이 소리 $n$가지를 전부 담는지만 확인하면 된다.