Description

给定一个长度为<math xmlns="http://www.w3.org/1998/Math/MathML">n的序列 <math xmlns="http://www.w3.org/1998/Math/MathML">a1,a2,...,an ，请问多少种方案，能够从中选取一个长度恰好为 <math xmlns="http://www.w3.org/1998/Math/MathML">m 的子段，且子段内所有数字的最大值不超过<math xmlns="http://www.w3.org/1998/Math/MathML">K？

Input Format

输入共两行：
输入第一行，三个正整数<math xmlns="http://www.w3.org/1998/Math/MathML">n,m,K
输入第二行，<math xmlns="http://www.w3.org/1998/Math/MathML">n个整数<math xmlns="http://www.w3.org/1998/Math/MathML">a1,a2,...,an 。

Output Format

输出一个整数，表示方案数。

5 2 5
3 7 2 5 1

2

Hint

样例解释

选取{2,5}和{5,1}均可，共两种方案

• 对于 <math xmlns="http://www.w3.org/1998/Math/MathML">30% 的数据，<math xmlns="http://www.w3.org/1998/Math/MathML">1≤m≤n≤10
• 对于 <math xmlns="http://www.w3.org/1998/Math/MathML">60% 的数据，<math xmlns="http://www.w3.org/1998/Math/MathML">1≤m≤n≤103
• 对于 <math xmlns="http://www.w3.org/1998/Math/MathML">100% 的数据，<math xmlns="http://www.w3.org/1998/Math/MathML">1≤m≤n≤105 且<math xmlns="http://www.w3.org/1998/Math/MathML">−109≤ai,K≤109

Source

前缀和 连续区间 上海市2023年3月赛