P4919 Marisa Picks Mushrooms

$\text {Marisa}$ is a girl who loves magic, and the high-firepower and flashy Bagua Furnace is her commonly used weapon. As time goes on, $\text {Marisa}$ also wants to upgrade the firepower of her Bagua Furnace, so she decides to go to the Magic Forest to pick mushrooms to obtain materials for experiments.

$\text {Marisa}$ arrives in the forest and sees a row of $n$ colorful mushrooms. Their colors are $a_1,a_2,\cdots,a_n$. Since she is very picky, she will only pick those “magic mushrooms”. A mushroom is called a “magic mushroom” if and only if it is **within a given interval**, and within this given interval, the difference between the number of mushrooms with the same color as it (including itself) and the number of mushrooms of that color outside this given interval is less than or equal to a given constant $k$. Now $\text {Marisa}$ will make $m$ queries. In the $i$-th query, you need to answer how many different colors of “magic mushrooms” there are in $[l_i,r_i]$.

The first line contains three integers $n,m,k$. The second line contains $n$ positive integers, representing the color $a_i$ of each mushroom. Then follow $m$ lines, each containing two positive integers $l_i,r_i$, representing the left endpoint and right endpoint of the interval queried by $\text{Marisa}$. The data guarantees that $0 < l_i \le r_i \le n$.

Output $m$ lines. Each line contains an integer $x$, representing the number of **different colors** of “magic mushrooms” in the query interval.

#### Sample Explanation: Let the constant $k=2$. For the interval $[1,2]$: $a_1=2$. Mushrooms of color $2$ appear $1$ time inside $[1,2]$, and $2$ times outside the interval. The difference is $|1-2|=1