가까운 지배자 탐색
오른쪽에서 더 큰 값처럼 가까운 비교 대상을 찾으면 스택 후보가 됩니다.
지배된 후보를 버릴 수 있으면 단조 구조를 쓴다
단조 스택과 단조 큐는 남겨야 할 후보와 버려도 되는 후보의 경계를 불변식으로 표현합니다.
만료 인덱스 제거
구간 밖 인덱스가 답이 될 수 없으면 큐 앞쪽 만료 처리가 필요합니다.
선형 시간 근거
pop된 원소가 다시 답이 되지 않는다는 근거가 있어야 선형 시간이 됩니다.
스택 선택
현재 값이 이전 후보를 지배하면 뒤에서 제거하고 인덱스를
기록합니다.
큐 선택
구간 왼쪽 경계와 값 단조성을 동시에 유지합니다.
반례 점검
같은 값 처리와 끝 인덱스 포함 여부를 작은 배열로 재현합니다.