Description

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

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

现在 $\text {Marisa}$ 会做出 $m$ 个询问，第 $i$ 个询问中，你需要回答 $[l_i,r_i]$ 中有多少种不同颜色的“魔法蘑菇”。

Input Format

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

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

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

Output Format

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

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

2
3
3

Hint

样例解释：

常数 $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]$ 中有两种颜色不同的魔法蘑菇。

数据范围：

对于全部数据，$1\le a_i \le 10^6$，$1 \le l_i \le r_i \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: 请注意读入效率。