미리 듣기의 곡 가짓수

문제

음악 스트리밍 서비스는 이용자의 재생 기록에서 연속된 일부를 골라 미리 듣기 목록으로 제공하려 한다. 재생 기록에는 곡을 끝까지 들은 순서대로 N개의 곡 번호가 적혀 있다. 같은 곡을 여러 번 들었다면 같은 번호가 여러 위치에 나타날 수 있으며, 재생 시각이나 곡의 길이는 이번 작업에서 고려하지 않는다. 미리 듣기 목록은 재생 기록에서 시작 위치와 끝 위치를 하나씩 정하여 만든다. 시작 위치부터 끝 위치까지의 기록을 빠짐없이 가져와야 하며, 중간의 곡을 건너뛰거나 순서를 바꿀 수 없다. 시작 위치와 끝 위치는 같아도 된다. 따라서 한 곡의 재생 기록만 가져오는 목록도 허용하지만, 아무 기록도 가져오지 않는 빈 목록은 허용하지 않는다. 담당자는 미리 듣기 목록에 정확히 K가지의 곡이 포함되기를 원한다. 곡의 가짓수는 목록에 등장하는 서로 다른 곡 번호의 개수다. 같은 곡이 여러 번 등장하더라도 가짓수에는 한 번만 센다. 목록에 포함된 전체 재생 횟수에는 별도의 제한이 없다. 예를 들어 서로 다른 두 곡이 번갈아 여러 번 등장하는 목록도 곡의 가짓수는 두 가지다. 가능한 목록을 셀 때는 곡 번호의 나열만 비교하지 않는다. 시작 위치 또는 끝 위치가 다르면 서로 다른 선택으로 센다. 그러므로 같은 곡 번호 하나를 담은 목록이라도 재생 기록의 서로 다른 위치에서 가져왔다면 각각 하나씩 세어야 한다. 전체 재생 기록과 정수 K가 주어질 때, 정확히 K가지의 곡을 포함하는 미리 듣기 목록의 수를 구한다. 조건을 만족하는 선택이 없으면 그 수는 0이다. 답은 가능한 시작 위치와 끝 위치의 쌍을 센 정수이며, 나머지를 구하지 않고 전체 값을 출력한다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1 ≤ N ≤ 200,000, 1 ≤ K ≤ 9이다.
둘째 줄에 재생 순서대로 곡 번호 A_1, A_2, ..., A_N이 공백으로 주어진다. 모든 곡 번호는 1 이상 9 이하의 정수다.

출력

정확히 K가지의 곡을 포함하는 비어 있지 않은 연속 구간의 수를 정수 하나로 출력한다.

5 2
2 5 2 7 5

5

4 1
6 6 6 6

10

5 3
1 8 1 8 8

0

출처: Devin.KR 자체 제작