3978. 零落尘

【题目背景】

零落成泥碾作尘，只有香如故。

【题目描述】

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

若一个区间 $[l, r]$（$1 \le l \le r \le n$）满足 $a_l, a_{l+1}, a_{l+2},\cdots, a_r$ 中不小于 $m$ 的元素数量不少于 $k$ 个，则称该区间为零落区间。

请求出该序列中，所有零落区间的个数。

【输入格式】

第一行三个正整数 $n, m, k$，意义见【题目描述】。

第二行 $n$ 个整数 $a_1, a_2, \cdots, a_n$，表示一个序列。

【输出格式】

一行一个正整数，表示所有零落区间的个数。

【样例1输入】

6 4 3
5 1 4 5 1 4

【样例1输出】

5

【样例1说明】

所有的零落区间为 $[2,6], [1,6], [3,6], [1,4], [1,5]$，共 $5$ 个。

【样例2输入】

6 9 2
1 9 1 9 8 10

【样例2输出】

8

【数据规模与约定】

对于 $30 \%$ 的数据，$1 \le n \le 500$ 。

对于 $60 \%$ 的数据，$1 \le n \le 5000$ 。

对于另外 $10 \%$ 的数据，$k=1$ 。

对于 $90 \%$ 的数据，$1 \le n \le 10^6$ 。

对于 $100 \%$ 的数据，$1 \le k \le n \le 5 \times 10^6$，$1 \le m, a_i \le 10^9$ 。

【来源】

2024年校际联合邀请赛 普及组-第1场 Task3