k小数查询

题号：NC218870
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛学会了可持久化线段树，于是他开始向牛妹炫耀。牛妹很不屑，那你能解决下面这道 ${k}$ 小数查询的问题吗：

给出长度为 ${n}$ 的序列 ${a_1,a_2,...,a_n}$ ，有多少对不同的整数对 $(l,r)(l\le r)$ 满足 $r-l+1\ge k$ 且 $a_l,a_{l+1},...,a_r$ 中第 ${k}$ 小的数是 ${x}$ ？

第一行三个整数。
第二行个整数。

一行一个整数表示答案。

示例1

复制

5 3 2
1 2 3 4 5

复制

区间第小的数都是。


为的一个排列。