민호가 관리하는 천나라에는 N개의 집이 있다. 민호는 집을 쉽게 관리하기 위해 각각의 집을 1번, 2번, … , N번으로 부르기로 했다.</p>

어느 날, 미적 감각에 눈을 뜬 홍준이는 천나라에 존재하는 모든 집에 페인트 칠을 했다.

이렇게 모두 페인트를 칠한 뒤 홍준이는 특정 구간에 있는 집들에 존재하는 페인트의 밝기들 중 가장 많은 것의 개수가 궁금해졌다.

이를 알아보는 프로그램을 만들어 보자.

입력 형식

첫 번째 줄에 N, Q (1 ≤ N ≤ 100,000, 1 ≤ Q ≤ 100,000)이 공백을 구분으로 주어진다.</p>

각각 천나라에 존재하는 집의 수와 민호가 궁금해 하는 특정 구간의 수이다.

두 번째 줄에는 1번 집부터 N번 집까지 차례대로 칠해진 페인트의 밝기(-100,000 ≤ P ≤ 100,000) 가 주어진다

세 번째 줄부터 Q개의 줄에 걸쳐 특정 구간이 주어진다. 이는 X, Y (1 ≤ X ≤ Y ≤ N) 으로 이루어 져 있으며 궁금해 하는 특정 구간이 X번 집부터 Y번 집까지라는 것을 의미한다.

출력 형식

Q개의 줄에 걸쳐 각 구간에 가장 많이 등장하는 페인트 밝기의 개수를 출력한다.

예제 입력

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

예제 출력

2
4
2