Background

$\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.

Problem Description

$\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]$.

Input Format

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 Format

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

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

2
3
3

Hint

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<2$.

$a_2=3$. Mushrooms of color $3$ appear $1$ time inside $[1,2]$, and $0$ times outside the interval. The difference is $|1-0|=1<2$.

So there are two different colors of magic mushrooms in $[1,2]$.

Constraints:

For all testdata, $1\le a_i \le 10^6$, $1 \le l_i \le r_i \le n$.

For $20\%$ of the testdata, $1 \le n,m \le 100$, $0 \le k \le 5$.

For $50\%$ of the testdata, $1 \le n,m \le 10^5$, $0 \le k \le 100$.

For $100\%$ of the testdata, $1 \le n,m \le 10^6$, $0 \le k \le 10^4$.

ps: Please pay attention to input efficiency.

Translated by ChatGPT 5