Flower Picking Princess

In an ancient country, Princess Xiao Xun'er loves to pick flowers. The royal garden contains $$n$$ flowers arranged in a row, and each flower has one of $$c$$ colors, represented by integers $$1,2,\ldots, c$$. When picking flowers, the princess wants to maximize her happiness by collecting as many different colors as possible. However, she has a peculiar habit: she does not allow herself to end up with a color that occurs only once in her collection. In other words, for any color that appears in her picked segment, its frequency must be either 0 or at least 2.

Due to time constraints, she can only walk along one contiguous segment of the garden. Her maid, Fuhan Jie, has planned $$m$$ itineraries, each representing a contiguous segment of the garden. For each itinerary, determine how many distinct colors the princess can end up with (i.e. colors that appear at least twice in that segment).

The mathematical formulation is as follows:

For a given segment from index $$l$$ to $$r$$, let the number of flowers of a given color $$i$$ be $$f_i$$. The result for that segment is the count of colors for which $$f_i \ge 2$$.

inputFormat

The first line contains three integers $$n$$, $$c$$, and $$m$$, where $$n$$ is the number of flowers, $$c$$ is the number of colors, and $$m$$ is the number of itineraries/queries.

The second line contains $$n$$ space-separated integers, where each integer is in the range $$[1, c]$$, representing the colors of the flowers in order.

Each of the following $$m$$ lines contains two integers $$l$$ and $$r$$ (1-indexed), representing the start and end indices of the contiguous segment of the garden that the princess will pick.

outputFormat

For each query, output a single line containing one integer — the number of distinct colors in the segment that appear at least twice.

sample

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

1
1
1