CERN

CERN is an international organization that studies nuclear physics and elementary particle physics. The particle accelerator system at CERN runs experiments that collide particles at high speed.

There are $N$ particles in a row. Each particle has a type $v_i$, a natural number between $1$ and $N$.

You will run $Q$ experiments. In the $i$-th experiment, you observe the particles from position $l_i$ to position $r_i$ ($l_i < r_i$). Among the observed particles, you may pick any two particles of different types and collide them. Both particles are destroyed. Repeat this while the observed particles include two particles of different types. An experiment ends when all observed particles are destroyed or when only particles of one type remain. Depending on which particles you collide and in what order, the final remaining types can differ.

Collisions are expensive, so the experiments are run only in theory. For each experiment, find the number of particle types for which the experiment can end with some number of particles of that type remaining.

The first line contains the natural numbers $N$ and $Q$, the number of particles and the number of experiments.

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

Each of the next $Q$ lines contains two natural numbers $l_i$ and $r_i$ ($1 \le l_i < r_i \le N$), the observed interval in the $i$-th experiment.

For each of the $Q$ experiments, print the answer on its own line: the number of particle types that can remain at the end of the experiment.

In all subtasks, $2 \le N \le 500000$ and $1 \le Q \le 500000$.

In the first experiment, we can collide particles of types 3 and 4, which leaves two particles of type 2. No other type can remain.

In the second experiment, each type can be made to remain with some number of particles.

In the fourth and fifth experiments, some number of particles of type 4 remain no matter which collisions are chosen.