Frequent values

프로그램 명: frequent

제한시간: 2 초

n 개의 정수 a1,a2,.ai..aj..,an 이 오름차순으로 주어질 때 i , j (1 <= i <= j <= n)사이의 최빈수(최고의 빈도수)의 빈도를 구하는것이다.

첫 줄에 두 개의 수 n , q 가 입력으로 주어진다. (1 ≤ n, q ≤ 100000). n 은 수의 개수이고 , q 는 질의 수이다.

다음 줄에는 a1 부터 an 까지의 수가 주어지고 (-100000 ≤ ai ≤ 100000) 다음 q 줄에는 구간 i , j 가 주어진다.

각 질의에 대한 최빈수의 빈도수를 출력한다.

입력

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

출력

1
4
3

출처: Ulm Local 2007