시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB61030524451.586%

문제

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

어느 날 미적 감각에 눈을 뜬 민호는 천나라에 존재하는 모든 집에 페인트 칠을 했다. 하지만 페인트마다 밝기가 다 다르기 때문에 자짓 잘못하다가는 미관을 해칠 수 있다고 생각을 해 집의 번호가 증가한다면 어두워 지지 않는 방향으로 페인트를 칠하였다.

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

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

입력

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

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

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

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

출력

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

예제 입력 1

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

예제 출력 1

1
4
3