페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8503
서브태스크

적어도 하나씩 만들기 5s 1024MB

문제

길이 N의 수열이 주어진다.

정수 K에 대해, 다음의 조건을 만족하는 구간을 'K-좋은 구간'이라 정의하자.

  • 1\leq x\leq K를 만족하는 모든 x에 대해, 구간 내에 정확히 x개 존재하는 숫자가 적어도 하나 존재한다.

어떤 수열과 정수 K가 주어졌을 때, K-좋은 구간의 개수를 구해보자.


입력

첫 줄에 N과 K가 공백으로 구분되어 주어진다. (1\leq N\leq 10^5 , 1\leq K\leq 4)

그 다음 줄에 길이 N의 수열이 주어진다. 각 원소는 1 이상 N 이하의 자연수이다.


출력

주어진 수열에 대해 K-좋은 구간의 개수를 한 줄에 출력하여라.


부분문제

번호 점수 조건
#120점

N\leq 1000

#215점

수열의 모든 원소는 1 이상 K 이하의 자연수이다.

#335점

K=1

#430점

추가 제한 조건 없음


예제 #1

3 1
1 2 1
6

모든 구간이 1-좋은 구간이다.


예제 #2

6 3
6 5 6 4 5 5
1

전체 구간이 유일한 3-좋은 구간이다.


예제 #3

6 2
5 4 5 2 6 5
5


출처

COCI 2024/2025 Contest #1
로그인해야 코드를 작성할 수 있어요.