시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 610 | 305 | 244 | 51.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개의 줄에 걸쳐 각 구간에 가장 많이 등장하는 페인트 밝기의 개수를 출력한다.
10 3 -1 -1 1 1 1 1 3 10 10 10 2 3 1 10 5 10
1 4 3