Frequent Values
You are given a sequence of \(n\) integers \(a_1, a_2, \ldots, 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, \ldots, a_j\).
Input
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 10^6)\). The next line contains \(n\) integers \(a_1, \ldots, a_n\) \((-10^5 \leq a_i \leq 10^5)\), for each \(i \in \{ 1, \ldots, n\}\) separated by spaces. You can assume that for each \(i \in \{ 1, \ldots, 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.
Output
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
0Sample Output
1
4
3
Comments
Mise à jour du problème : on m'a signalé une erreur de formatage pour le troisième test (merci Jin !), à laquelle Python était sensible mais pas C++, que j'avais utilisé pour tester le jeu de tests. Le problème est réglé, et les soumissions ont été réévaluées. Désolé du temps que vous avez perdu pour le debug !