Description
Hey, can I say something amazing? Culturing bacteria is forbidden at school. Your Petri dish(培養皿) will be forfeited if caught by the teachers.
The Petri dishes are placed on the table in a row. Each Petri dish contains a kind of bacteria, labeled with an integer. Two bacteria of the same species will be labeled with the same integer, while two bacteria with different species will be labeled with different integers.
The teacher wants to know that how many species of bacteria he will get if he forfeits the within some range of the table. Given the number of Petri dish N and their species s0, s1, ..., sN-1, the teacher gave you Q queries. For each query, the teacher gave you two integer L and R. You have answer how many species of bacteria there are in range sL, ..., sR.
Input
There are two integers N, Q, begin the number of Petri dish and the number of queries.
The second line are N integers s0, s1, ..., sN-1, being the species of the bacteria.
The following Q lines are queries. Each query occupies a line and contains two integers L and R.
Technical Restrictions
-
1 ≦ N ≦ 1000000
-
1 ≦ Q ≦ 1000000
-
0 ≦ si ≦ 31
-
0 ≦ L ≦ R < N
Test Case Info
-
For the first test case, it is same as sample IO, suggested to use the first test case to check whether your output format is valid.
-
For the test cases from the second to the fifth, you can get an AC by purely by implementing this problem. No additional optimization is required.
-
For the test cases from the sixth to the eighth , some optimization is required. Recall that :
How to estimate the running time of your code?
A usual computer can run 10^9 basic operations (such as +, -, &, |) in 1 second. Although this depends on the judging server, this number serves as a good estimation for the running time of your code. Try to figure out how much operations your code needs to execute to finish all the computations (since not all operations in your code are basic operations, another estimate criterion is 10^8 operations (+, -, *, /, =, ...) in 1 second)!
Output
For each query, please output how many species of bacteria there are in the given range. Remember to add a new line character after every output.
Explanation of sample IO
For the first query (see orange range), in range [5, 6] there is one bacteria of species 1 and one bacteria of species 0. Since there are two kind of species, output 2. For the second query (see purple range), in range [3, 5] there are two bacteria of species 3 and one bacteria of species 1. Since there are two kind of species, output 2.
