Croatian Olympiad in Informatics
April \(28^{st}\) 2024
CERN is an international institution focused on nuclear research and particle physics. The particle
accelerator system at CERN is used to conduct experiments involving the collision of particles at high
speeds.
We consider \(N\) particles arranged in a sequence. Each particle is defined by its type \(v_{i}\), represented by a
positive integer between 1 and \(N\).
In the latest research, it is necessary to conduct \(Q\) experiments. In the \(i-th\) experiment, we observe all
particles from the \(l@@RISE_MATH_BLOCK_0@@i-th\) in the sequence (\(l@@RISE_MATH_BLOCK_1@@i\)). Among the observed particles, we can
choose any two particles of different types and collide them in the accelerator, causing both particles to be
destroyed. We repeat this collision process as long as there are two particles of different types among the
observed particles. The experiment ends either when all observed particles are destroyed or when there
are some particles of the same type remaining. Of course, depending on the order in which we collide the
particles, it is possible to end up with various types of particles at the end.
Since particle collision is not cheap, you have decided to conduct experiments only in theory. Now, for
each experiment, you are interested in how many types of particles exist such that it is possible to end
the experiment with some remaining particles of that type.

In all subtasks, \(2 \le N \le 500\), 000 and \(1 \le Q \le 500\), 000.
Subtask
Score
Constraints
1
13
\(v\)\(i \le 10\) for each \(i = 1\), . . . , N.
2
19
There are at most two particles of each type.
3
17
N, \(Q \le 2000\)
4
19
N, \(Q \le 100\), 000
5
32
There are no additional constraints.
Croatian Olympiad in Informatics
April \(28^{st}\) 2024
Example
input
11 5
2 4 2 3 4 4 3 1 4 4 4
1 4
2 8
6 9
8 10
8 11
output
1
4
1
1
1
Explanation of the first example:
In the first experiment, we can collide particles of types 3 and 4, leaving two particles of type 2 remaining.
There is no way to end up with any other type of particles.
In the second experiment, it is possible to end up with some remaining particles of each type.
In the fourth and fifth experiments, regardless of the choice of collisions, some particles of type 4 will
remain at the end.

The first line contains two positive integers \(N\) and \(Q\), the number of particles and the number of
experiments, respectively.
The next line contains a sequence of \(N\) numbers \(v_{1}\), . . . , v_{N}, representing the types of particles.
In each of the following \(Q\) lines, there is a pair of two positive integers \(l@@RISE_MATH_BLOCK_0@@i\) (\(1 \le l@@RISE_MATH_BLOCK_1@@i \le N\)),
representing the interval of observed particles in the \(i-th\) experiment.

For each of the \(Q\) experiments, print in a separate line the requested number of types of particles with
which it is possible to end the experiment.

생성자가 기록되지 않았습니다.

출처 COCI 2023/2024 Olympiad