화려한 마을 2

민호가 관리하는 천나라에는 집이 $N$개 있고, 각 집에는 1번부터 $N$번까지 번호가 붙어 있다.

어느 날 미적 감각에 눈을 뜬 민호는 천나라의 모든 집에 페인트를 칠했다. 페인트마다 밝기가 달라서 아무렇게나 칠하면 자칫 마을의 미관을 해칠 수 있다고 생각한 민호는, 집 번호가 커질 때 페인트가 어두워지지 않도록 칠했다. 즉 $i$번 집의 밝기는 $i+1$번 집의 밝기보다 밝지 않다.

칠을 마친 민호는 특정 구간에 있는 집들의 밝기 중 가장 많이 나온 밝기가 몇 번 나왔는지 궁금해졌다. 민호가 묻는 구간마다 그 개수를 구하는 프로그램을 작성하라.

첫째 줄에 집의 수 $N$과 민호가 묻는 구간의 수 $Q$가 공백으로 구분되어 주어진다. ($1 \le N \le 100000$, $1 \le Q \le 100000$)

둘째 줄에 1번 집부터 $N$번 집까지 칠해진 페인트의 밝기 $P_1, P_2, \dots, P_N$이 순서대로 주어진다. ($-100000 \le P_i \le 100000$이고, 모든 $i$에 대해 $P_i \le P_{i+1}$이다.)

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

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 구간에서 가장 많이 등장한 밝기의 등장 횟수를 출력한다.