# COI 24 Cern

https://www.acmicpc.net/problem/31981

CERN is an international organization focused on nuclear research and elementary particle physics. The particle accelerator system at CERN is used to conduct experiments involving high-speed particle collisions.

We are observing $N$ particles arranged in a sequence. Each particle is specified by its type $v_i$, represented by a natural number 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_i$-th to the $r_i$-th in the sequence ($l_i < r_i$). Among the observed particles, we can select any two particles of different types and collide them in the accelerator, causing both particles to be destroyed. This collision process is repeated 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 some number of particles of the same type remain. Of course, depending on the order and choice of particles collided, it is possible to end up with various types of remaining particles.

Since particle collisions are not cheap, you have decided to conduct the experiments only in theory. Now, for each experiment, you are interested in the number of types of particles such that it is possible to end the experiment with some number of remaining particles of that type.

## Input

In the first line are the natural numbers $N$ and $Q$, representing the number of particles and the number of experiments, respectively.

In the next line is a sequence of $N$ numbers $v_1, \dots, v_N$, representing the types of particles.

In the $i$-th of the next $Q$ lines is a pair of natural numbers $l_i$ and $r_i$ ($1 \le l_i < r_i \le N$) representing the observed interval of particles in the $i$-th experiment.

## Output

For each of the $Q$ experiments, output the desired number of particle types with which it is possible to end the experiment in a separate line.

## Subtasks

In all subtasks, it holds that $2 \le N \le 500,000$ and $1 \le Q \le 500,000$.

## Sample

### 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

In the first experiment, we can collide particles of types $3$ and $4$, leaving two particles of type $2$. There is no way to end with another type of particle.

In the second experiment, it is possible for each type of particle to end up with some number of particles of that type.

In the fourth and fifth experiments, regardless of the choice of collisions, some number of particles of type $4$ will remain in the end.