Description

Xiao Xun'er is the princess of an ancient kingdom, and one of her hobbies is picking flowers.

Today the weather is fine and sunny, so the princess went to the newly built palace garden in the morning to pick flowers.

The garden is large enough to hold $n$ flowers in total, with $c$ colors labeled by integers $1 \sim c$. The flowers are arranged in a single row to make it convenient for the princess to pick. After each picking session, the princess counts how many different colors she has collected; the more colors, the happier she is. At the same time, she has a quirk: she does not allow that, among the flowers she finally picks, any color appears only once. For this reason, every time she picks a flower, either she has already picked a flower of that color before, or her accurate intuition tells her she will be able to pick that color again.

Due to time constraints, the princess can only walk through one continuous segment of the garden to pick flowers, so the maid Fuhan Jie arranged $m$ trips after considering various factors. For each trip, you are asked how many different colors the princess can collect.

Input Format

The first line contains three space-separated integers, representing the number of flowers $n$, the number of colors $c$, and the number of trips $m$.

The second line contains $n$ space-separated integers. The $i$-th integer is the color $x_i$ of the $i$-th flower.

From line $3$ to line $(m + 2)$, each line contains two integers $l, r$. On line $(i + 2)$, the numbers represent that the $i$-th trip covers flowers from the $l$-th to the $r$-th.

Output Format

Output $m$ lines, one integer per line. The integer on the $i$-th line is the number of different colors the princess can collect on the $i$-th trip.

5 3 5
1 2 2 3 1
1 5
1 2
2 2
2 3
3 5

2
0
0
1
0

Hint

Explanation for Sample 1:

There are five flowers, and their colors are $1,~2,~2,~3,~1$.

For the first trip, the picking interval is $[1, 5]$. She can pick the flowers at positions $1,~2,~3,~5$, so there are two different colors, $1$ and $2$.

For the second trip, the picking interval is $[1, 2]$, but the flowers of colors $1$ and $2$ each appear only once, so the princess cannot pick any flower.

For the third trip, the picking interval is $[2, 2]$, but color $2$ appears only once, so the princess cannot pick any flower.

For the fourth trip, the picking interval is $[2, 3]$. She can pick the flowers at positions $2,~3$, and there is only one color, $2$.

For the fifth trip, the picking interval is $[3,5]$, but colors $1, 2, 3$ each appear only once, so the princess cannot pick any flower.

Constraints:

This problem uses bundled multi-test-point evaluation and has two subtasks.

For subtask $1$ (worth $100$ points), it is guaranteed that $1 \leq n, c, m \leq 3 \times 10^5$.

For subtask $2$ (worth $100$ points), it is guaranteed that $1 \leq n, c, m \leq 2 \times 10^6$.

For all test points, it is guaranteed that $1 \leq x_i \leq c$, $1 \leq l \leq r \leq n$.

Translated by ChatGPT 5