Background

Source: https://hsin.hr/hio2024/. This translation comes from Wenxin Yiyan. If you have a better translation, please provide it in the discussion section.

Problem Description

CERN is an international organization focusing on nuclear research and particle physics. CERN's particle accelerator system is used for high-speed particle collision experiments.

We consider $N$ particles arranged in a sequence. Each particle is defined by its type $v_i$, where $v_i$ is a positive integer between $1$ and $N$.

In the latest research, $Q$ experiments need to be conducted. In the $i$-th experiment, we observe all particles in the sequence from the $l$-th to the $r$-th (where $l < r$). Among the observed particles, we may choose any two particles of different types and collide them in the accelerator, causing both particles to be destroyed. We repeat this collision process until there are no two particles of different types among the observed particles. The experiment ends when all observed particles are destroyed, or only particles of the same type remain. Of course, depending on the order in which we choose particles to collide, different types of particles may remain in the end.

Since particle collisions are expensive, you decide to conduct the experiments only in theory. Now, for each experiment, you are interested in how many particle types are such that, when the experiment ends, it is possible that particles of that type remain.

Input Format

The first line contains two positive integers $N$ and $Q$, representing the number of particles and the number of experiments.

The second line contains $N$ numbers $v_1, \dots, v_N$, representing the types of the particles.

In the next $Q$ lines, each line contains two positive integers $l$ and $r$ ($1 \leq l < r \leq N$), representing the particle interval observed in the $i$-th experiment.

Output Format

For each experiment, output on a separate line the number of particle types that can possibly remain when the experiment ends.

11 5
2 4 2 3 4 4 3 1 4 4 4
1 4
2 8
6 9
8 10
8 11

1
4
1
1
1

Hint

Sample Explanation

In the first experiment, we can collide a type $3$ particle with a type $4$ particle, leaving two type $2$ particles. It is impossible to end up with any other type of particle.

In the second experiment, it is possible that some particles of every type remain in the end.

In the fourth and fifth experiments, no matter which collision method is chosen, some type $4$ particles will remain in the end.

Constraints

Across all subtasks, $2 \leq N \leq 5\times 10^5$ and $1 \leq Q \leq 5\times 10^5$.

• Subtask 1 (13 points): For each $i = 1, \dots, N$, $v_i \leq 10$.
• Subtask 2 (19 points): Each particle type appears at most twice.
• Subtask 3 (17 points): $N, Q \leq 2\times 10^3$.
• Subtask 4 (19 points): $N, Q \leq 1\times 10^5$.
• Subtask 5 (32 points): No additional constraints.

Translated by ChatGPT 5