백설공주와 난쟁이
시간 제한1초메모리 제한256 MB
모자 색상 수열이 주어질 때 각 구간에 과반수를 차지하는 색이 있는지 판별하고 그 색을 찾는 문제입니다.
문제
백설공주는 숲속에서 N명의 난쟁이와 함께 산다. 난쟁이들은 매일 아침 한 줄로 서서 광산으로 출근하고, 백설공주는 그 모습을 사진으로 찍는다.
각 난쟁이는 모자를 쓰고 있으며, 모자의 색상은 1번부터 C번까지의 자연수로 표현된다. 어떤 사진에 K명의 난쟁이가 찍혀 있을 때, 그중 절반보다 많은 난쟁이가 같은 색 모자를 쓰고 있다면 그 사진은 예쁜 사진이다.
백설공주가 찍은 사진 M장이 주어진다. 각 사진은 줄에서 연속한 난쟁이들의 구간으로 주어진다. 각 사진이 예쁜 사진인지 판별하고, 예쁜 사진이라면 절반보다 많이 등장한 모자 색을 출력하시오.
입력
첫째 줄에 난쟁이의 수 N과 모자 색상의 수 C가 주어진다. (3 <= N <= 300,000, 1 <= C <= 10,000)
둘째 줄에는 줄에 선 순서대로 각 난쟁이의 모자 색상이 주어진다. 색상은 C 이하의 자연수이다.
셋째 줄에는 사진의 수 M이 주어진다. (1 <= M <= 10,000)
다음 M개의 줄에는 두 정수 A와 B가 주어진다. (1 <= A <= B <= N) 이는 A번째 난쟁이부터 B번째 난쟁이까지가 사진에 찍혔다는 뜻이다.
출력
총 M줄을 출력한다. 해당 사진이 예쁘지 않다면 no를 출력한다. 예쁜 사진이라면 yes X를 출력한다. 이때 X는 사진에 찍힌 난쟁이 중 절반보다 많이 등장한 모자 색이다.