Particle Collision Survivors

CERN, an international institution devoted to nuclear and particle physics research, uses a series of high-speed particle collision experiments. In a new series of experiments, you are given a sequence of N particles in order. Each particle is characterized by its type v_i, where v_i is an integer between 1 and N.

There will be Q experiments. In the i-th experiment, you observe the subarray of particles from index l to index r (with l < r). During the observation, you are allowed to repeatedly select any two particles of different types from the observed set and collide them in the accelerator, which destroys both particles. This collision process continues until either all observed particles are destroyed or only particles of a single type remain.

Because the cost of collision experiments is very high, you have decided to simulate them theoretically. For each experiment, you are interested in determining the number of particle types for which it is possible that the experiment ends with particles of that type remaining.

More formally, let the observed subarray have a multiset of particles. For any particle type t that appears with frequency f_t, let the total number of particles be S and the number of particles not of type t be r_other = S - f_t. If the non-t particles are optimally paired off among themselves, the leftover non-t particles will be those of the most frequent type among them. Denote M_other as the maximum frequency among types other than t (if any exist), so that the leftover count is

\( L = \max\{0, 2 \cdot M_{other} - r_{other} \} \)

Then it is possible for type t to be the sole survivor if and only if f_t > L (note that if all particles are already of the same type, then that type qualifies).

Your task is, for each experiment, to compute the number of particle types that could possibly be the final surviving type.

inputFormat

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

The second line contains N integers v₁, v₂, ..., v_N, where v_i represents the type of the i-th particle (1 ≤ v_i ≤ N).

Each of the following Q lines contains two integers l and r (with l < r), representing an experiment on the subarray from l to r.

outputFormat

For each experiment, output a single integer on a separate line --- the number of distinct particle types which can possibly be the only surviving type at the end of the experiment.

sample

3 1
1 2 3
1 3

3