The longest road of the Fairy Kingdom has n
milestones. A long-established tradition defines a specific color for
milestones in each region, with a total of m colors in the
kingdom. There is a map describing all milestones and their colors.
A number of painter teams are responsible for
milestone maintenance and painting. Typically, each team is assigned a road
section spanning from milestone #l to milestone #r.
When optimizing the assignments, the supervisor often has to determine how many
different colors it will take to paint all milestones in the section l…r.
Example. Suppose there are five milestones #1, #2, #3,
#4, #5 to be painted with colors 1, 2, 3, 2, 1, respectively. In this case,
only two different paints are necessary for milestones 2…4: color 2 for
milestones #2 and #4, and color 3 for milestone #3.
Write a program that, given a map, will be able
to handle multiple requests of the kind described above.
Limitations
1 <= n <= 10 000; 1<= m <= 255; 1 <= li <= ri <= n; 1 <= k <= 100 000.
Input
The first line contains two integers, n and k – the number of milestones and the number of
requests, respectively. The second line consists of n integers separated by spaces and defines the
sequence of colors for milestones from #1 to #n. The following k lines
contain pairs of
integers, one pair per line.
Each pair consists of two numbers – li and ri
– and
defines a range of milestones for request i.
Output
The output file should contain k integers separated by line breaks. Result number i
should present the result of the i-th
request, i. e. the number of colors required to paint all milestones in the road section li…ri.
Example
Input
|
Output
|
|
5 3
1 2 3 2 1
1 5
1 3
2 4
|
3
3
2
|
All Rybinsk-2012 problems (in PDF)
