U501421 顏色Colour

有一个颜色序列 $a_1,a_2,...,a_n$。 AquaZhao 想问你，对于一些区间 $[l,r]$，$a_l,a_{l+1},...,a_r$ 中共有几种颜色。但是他觉得这题[太简单了](https://www.luogu.com.cn/problem/P1972)。 于是他改为问你区间中有几种颜色出现过至少两次。但是 AquaZhao 觉得这肯定也[难不倒你](https://www.luogu.com.cn/problem/P4113)。 于是——

给你一个颜色序列 $a$ 、一个参数 $k$（输入开头给定）和 $m$ 个区间询问 $[l,r]$。你需要回答 $a_l,a_{l+1},...,a_r$ 中共有几种颜色出现过至少 $k$ 次。

第一行是三个用空格隔开的整数，分别代表颜色序列长度 $n$，询问数 $m$，以及参数 $k$。输入数据保证 $k \le n$。 第二行是 $n$ 个用空格隔开的整数，第 $i$ 个整数代表第 $i$ 个颜色种类 $a_i$。 接下来 $m$ 行，每行两个整数 $l,r$，代表区间 $[l,r]$。

输出共 $m$ 行，每行一个整数。第 $i$ 行的整数代表第 $i$ 个询问的答案。

对于 $30\%$ 数据，$1 \le n,m,k,a_{i} \le 3000$。 对于另外 $10\%$ 数据，$k=1$。 对于另外 $10\%$ 数据，$k=2$。 对于全部数据，保证 $1 \le n,m,k,a_{i} \le 10^{6}$ 并且 $k \le n$。