화려한 마을 3

민호가 관리하는 천나라에는 집이 $N$개 있다. 민호는 집을 관리하기 편하도록 각 집에 1번부터 $N$번까지 번호를 붙였다.

어느 날 홍준이가 천나라의 모든 집에 페인트를 칠했다. 한 집에 칠한 페인트의 밝기는 정수 하나로 나타낸다.

칠을 마친 뒤 홍준이는 어떤 구간에 있는 집들의 페인트 밝기 중 가장 많이 나온 밝기가 몇 번 나오는지 궁금해졌다.

구간마다 그 횟수를 구하는 프로그램을 작성하시오.

첫째 줄에 집의 수 $N$과 궁금한 구간의 수 $Q$가 공백으로 구분되어 주어진다. ($1 \le N \le 100\,000$, $1 \le Q \le 100\,000$)

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

셋째 줄부터 $Q$개의 줄에 걸쳐 구간이 한 줄에 하나씩 주어진다. 각 줄은 두 정수 $X$, $Y$로 이루어지며 $X$번 집부터 $Y$번 집까지를 뜻한다. ($1 \le X \le Y \le N$)

$Q$개의 줄에 걸쳐 각 구간에서 가장 많이 등장하는 밝기의 등장 횟수를 입력에 주어진 순서대로 출력한다.