[R1E]过分的子区间 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的正整数数组 $A$，将 $A$ 的第 $l$ 位到第 $r$ 位称为子区间 $[l,r]=\{A_l,A_{l+1},...,A_r\}$。如果子区间中第 $k$ 小的数大于等于 $x$，我们称这个子区间是“过分的”。

特别提醒，如果子区间长度小于 $k$，那么这个子区间一定是过分的。

请问数组 $A$ 共有多少个子区间是过分的。

格式

输入格式

第一行包含三个正整数 $n$, $k$, $x$，分别表示数组 $A$ 的长度，以及定义“过分的”所用的参数。

第二行包含 $n$ 个正整数，表示数组 $A$。

输出格式

输出一个整数，表示数组 $A$ 共有多少个子区间是过分的。

样例

样例输入 #1

6 1 2
1 3 5 1 7 2

样例输出 #1

6

样例解释 #1

$6$ 个过分的子区间分别为：

①$[2,2]$，区间内第 $1$ 小的元素为 $3$；

②$[2,3]$，区间内第 $1$ 小的元素为 $3$；

③$[3,3]$，区间内第 $1$ 小的元素为 $5$；

④$[5,5]$，区间内第 $1$ 小的元素为 $7$；

⑤$[5,6]$，区间内第 $1$ 小的元素为 $2$；

⑥$[6,6]$，区间内第 $1$ 小的元素为 $2$。

数据规模

对于 $20\%$ 的数据，$n\leq 100$。

对于 $50\%$ 的数据，$n\leq 1000$。

对于 $100\%$ 的数据，$1\leq k \leq n\leq 2\times 10^5$， $1\leq x,A_i\leq 10^9$。