SP1684 FREQUENT - Frequent values

You are given a sequence of $n$ integers $a_{1},a_{2},\dots,a_{n}$ in non-decreasing order. In addition to that, you are given several queries consisting of indices $i$ and $j$ ($1 \leq i \leq j \leq n$). For each query, determine the most frequent value among the integers $a_{i},\dots,a_{j}$.

The input consists of several test cases. Each test case starts with a line containing two integers $n$ and $q$ ($1 \leq n,q \leq 100000$). The next line contains $n$ integers $a_{1}\dots,a_{n}$ ($-100000 \leq a_{i}\leq 100000$, for each $i \in {1,\dots, n}$) separated by spaces.You can assume that for each $i \in {1,\dots, n-1}$: $a_{i} \leq a_{i+1}$. The following $q$ lines contain one query each, consisting of two integers $i$ and $j$ ($1 \leq i \leq j \leq n$), which indicate the boundary indices for the query. The last test case is followed by a line containing a single $0$.

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