#P18871. [HONI 2024/2025 #1] Učiteljica

[HONI 2024/2025 #1] Učiteljica

题目描述

给定长度为 NN 的数列。你可以从开头和结尾各删去若干元素,保留一个连续子数组。对于每个 t=1,2,…,Kt=1,2,\ldots,K,保留的子数组中都必须至少有一种数值恰好出现 tt 次。

求满足条件的删除方案数。只要保留的位置集合不同,便视为不同方案。

输入格式

第一行两个整数 N,KN,K,满足 1≤N≤1051\le N\le10^5、1≤K≤41\le K\le4。第二行 NN 个整数 aia_i,满足 1≤ai≤N1\le a_i\le N。

输出格式

输出符合条件的删除方案数。

子任务

子任务 分值 额外限制
1 20 N≤1000N\le1000
2 15 所有 ai≤Ka_i\le K
3 35 K=1K=1
4 50 无

样例

样例 1

输入

3 1
1 2 1

输出

6

样例 2

输入

6 3
6 5 6 4 5 5

输出

1

样例 3

输入

6 2
5 4 5 2 6 5

输出

5