Page not loading? Try clicking here.
Placeholder

#8503
Subtask

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

Problems

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

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

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

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


Input

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

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


Output

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


Subtask

# Score Condition
#120

N\leq 1000

#215

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

#335

K=1

#430

추가 제한 조건 없음


Example #1

3 1
1 2 1
6

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


Example #2

6 3
6 5 6 4 5 5
1

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


Example #3

6 2
5 4 5 2 6 5
5


Source

COCI 2024/2025 Contest #1

You must sign in to write code.