题目背景

$\text {Marisa}$ 是一个爱魔法的女孩子，而火力高而华丽的八卦炉正是她常用的武器，随着时代的进步，$\text {Marisa}$ 也想要升级她的八卦炉的火力，所以她决定去魔法森林采蘑菇来获得做实验的材料

题目描述

$\text {Marisa}$ 来到了森林之中，看到了一排 $n$ 个五颜六色的蘑菇，这些蘑菇的颜色分别为 $a_1,a_2,...,a_n$ 。由于她很挑剔，所以她只会采那些"魔法蘑菇" 。

一个蘑菇被叫做"魔法蘑菇"，当且仅当它在给定的某段区间内，并且在这段给定区间内与它颜色相同的蘑菇(包括它本身)的个数，与在这个给定区间外这种颜色的蘑菇的个数之差小于等于给定的常数 $k$

现在 $\text {Marisa}$ 会做出 $m$ 个询问,每次询问你 $[l,r]$ 中有多少种不同颜色的"魔法蘑菇"

输入格式

第一行三个整数 $n,m,k$

第二行 $n$ 个正整数，表示蘑菇的颜色 $a_i$

之后 $m$ 行，每行两个正整数 $l_i,r_i$ ，表示 $\text{Marisa}$ 询问区间的左端点和右端点，数据保证 $0<l≤r≤n$

输出格式

共 $m$ 行，每行一个整数 $x$ ，表示询问区间中不同颜色的"魔法蘑菇"的种数

6 3 2
2 3 2 4 1 2
1 2
2 4
1 6

2
3
3

提示

样例解释:

常数 $k=2$ ，对于区间 $[1,2]$:

$a_1=2$，$2$这种颜色的蘑菇在区间 $[1,2]$ 内出现了 $1$ 次，在区间外出现了 $2$ 次，相差为 $|1-2|=1<2$

$a_2=3$，$3$这种颜色的蘑菇在区间 $[1,2]$ 内出现了 $1$ 次，在区间外出现了 $0$ 次，相差为 $|1-0|=1<2$

所以 $[1,2]$ 中有两种颜色不同的魔法蘑菇

数据范围:

对于全部数据，$a_i \le 10^6,1 \le l_i \le r \le n$

对于 $20\%$ 的数据，$1 \le n,m \le 100,0 \le k \le 5$

对于 $50\%$ 的数据，$1 \le n,m \le 10^5,0 \le k \le 100$

对于 $100\%$ 的数据，$1 \le n,m \le 10^6,0 \le k \le 10^4$

ps:请注意读入效率