3368 Frequent values

原文

時間制限:2000ミリ秒
メモリ制限:65536KB

頻出値

問題

単調非減少なn個の整数の列a1, a2, ... , anが与えられる。さらに、インデックスi,j(1 ≦ i ≦ j ≦ n)からなるクエリがいくつか与えられる。各クエリについて、ai , ... , ajのなかで最も多く出現する数(の出現する個数)を決定せよ。

入力

入力はいくつかのテストケースからなる。各テストケースは2つの整数nとq(1 ≦ n, q ≦ 100000)を含む1行からなる。次の行はn個の整数a1 , ... , an (各1≦i≦nについて-100000 ≦ ai ≦ 100000)が空白を区切りとして書かれている。各1≦i≦n-1についてai ≦ ai+1としてよい。続くq行はそれぞれ、2つの整数iとj(1 ≦ i ≦ j ≦ n)からなる1つのクエリを含み、クエリの範囲をあらわす。

最後のテストケースのあとには、0のみを含む行が続く。

出力

各クエリについて、1つの整数を含む1行を出力せよ: 与えられた範囲で最も多く出現する数の出現する回数。

入力例

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

出力例

1
4
3

出典

Ulm Local 2007