题目背景

译自 COCI 2024/2025 #1 T4。$\texttt{5s,0.5G}$。满分为 $120$。

题目描述

给定长度为 $n$ 的正整数序列 $a_1,a_2,\cdots,a_n$。给定常数 $k$。

求出满足以下条件的二元组 $(l,r)$ 的数量：

• $1\le l\le r\le n$；
• 对于任意 $1\le i\le k$，都存在一个数 $x$，使得 $x$ 在 $a_l,a_{l+1},\ldots,a_r$ 间出现恰好 $i$ 次。

输入格式

第一行，两个正整数 $n,k$。

第二行，$n$ 个正整数 $a_1,a_2,\cdots,a_n$。

输出格式

输出一行一个整数，表示答案。

3 1
1 2 1

6

6 3
6 5 6 4 5 5

1

6 2
5 4 5 2 6 5

5

提示

对于 $100\%$ 的数据，保证：

• $1\le n\le 10^5$；
• $1\le k\le 4$；
• $1\le a_i\le n$。

• 特殊性质 A：$1\le a_i\le k$。
• 特殊性质 B：$k=1$。