단조 구조

더 강한 후보가 오면 약한 후보는 즉시 버린다

예시 입력 2, 1, 3에서 3을 만나는 순간, 1과 2는 앞으로도 다음 큰 수의 답이 될 수 없어 제거된다.

입력 순서

2 1 3
1. push 2 아직 오른쪽의 더 큰 값을 모르는 후보다.
2. push 1 2보다 작으므로 같이 대기한다.
3. read 3 3이 1과 2의 답을 한 번에 확정한다.

스택 변화

before
2 1 top
pop
1 2 ans = 3
after
3 top

핵심 불변식: 각 인덱스는 한 번 들어오고 한 번만 나간다. 그래서 중첩 탐색이 아니라 선형 시간으로 끝난다.