頁面無法載入？點擊這裡可能會修復。
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

需要登入才能撰寫程式碼。