## FREQUENT - Frequent values

You are given a sequence of **n** integers
**a _{1} , a_{2} , ... , a_{n}**
in non-decreasing order. In addition to that, you are given several
queries
consisting of indices

**i**and

**j**(

*1 ≤ i ≤ j ≤ n*). For each query, determine the most frequent value among the integers

**a**.

_{i}, ... , a_{j}#### Input Specification

The input consists of several test cases.
Each test case starts with a line containing two integers **n**
and **q** (*1 ≤ n, q ≤ 100000*).
The next line contains **n** integers
**a _{1} , ... , a_{n}**
(

*-100000 ≤ a*, for each

_{i}≤ 100000*i ∈ {1, ..., n}*) separated by spaces. You can assume that for each

*i ∈ {1, ..., n-1}: a*. The following

_{i}≤ a_{i+1}**q**lines contain one query each, consisting of two integers

**i**and

**j**(

*1 ≤ i ≤ j ≤ n*), which indicate the boundary indices for the query.

The last test case is followed by a line containing a single *0*.

#### Output Specification

For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.

#### Sample Input

10 3 -1 -1 1 1 1 1 3 10 10 10 2 3 1 10 5 10 0

#### Sample Output

1 4 3

*A naive algorithm may not run in time!*

Added by: | Adrian Kuegel |

Date: | 2007-07-06 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |

Resource: | University of Ulm Local Contest 2007 |