P8883 - 选取子段

内存限制：128 MB 时间限制：0 S

题面：传统评测方式：文本比较上传者：

提交：1 通过：1

给定一个长度为

lns="http://www.w3.org/1998/Math/MathML"> �

的序列

lns="http://www.w3.org/1998/Math/MathML"> �_{1}, �_{2}, . . ., �_{�}

，请问多少种方案，能够从中选取一个长度恰好为

lns="http://www.w3.org/1998/Math/MathML"> �

的子段，且子段内所有数字的最大值不超过

lns="http://www.w3.org/1998/Math/MathML"> �

？

输入共两行：
输入第一行，三个正整数

lns="http://www.w3.org/1998/Math/MathML"> �, �, �

输入第二行，

lns="http://www.w3.org/1998/Math/MathML"> �

个整数

lns="http://www.w3.org/1998/Math/MathML"> �_{1}, �_{2}, . . ., �_{�}

。

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

5 2 5
3 7 2 5 1

样例解释

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

对于 $lns="http://www.w3.org/1998/Math/MathML"> 30 %$ 的数据， $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq � \leq � \leq 10$
对于 $lns="http://www.w3.org/1998/Math/MathML"> 60 %$ 的数据， $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq � \leq � \leq 1 0^{3}$
对于 $lns="http://www.w3.org/1998/Math/MathML"> 100 %$ 的数据， $lns="http://www.w3.org/1998/Math/MathML"> 1 \leq � \leq � \leq 1 0^{5}$ 且 $lns="http://www.w3.org/1998/Math/MathML"> - 1 0^{9} \leq �_{�}, � \leq 1 0^{9}$

8883: 选取子段