첫째 줄에 자연수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 카드의 초기 배열을 나타내는 N개의 정수가 빈 칸을 사이에 두고 순서대로 주어진다.
출력
첫째 줄부터 N-1개 줄에 걸쳐 합치는 과정을 표현해 줄 한 개의 정수를 출력한다. 합쳐질 두 개의 묶음 중, 앞 묶음의 마지막 카드가 몇 번째 카드인지를 출력하면 된다. 예를 들어, [6] [3 2 1] [4 5]의 경우, 앞 묶음인 [3 2 1]의 마지막 카드인 1은 네 번째이므로, 4를 출력하면 된다.
입력 예시
6
6 3 2 1 4 5
출력 예시
3
2
5
4
1
풀이
가능한 경우밖에 주어지지 않으므로, 스택으로 그리디하게 풀이해볼 수 있다.
총 N개의 인덱스를 순회하며 다음 과정을 시행한다.
스택의 최상위 노드와 현재 노드가 연속되는 경우(스택의 최댓값보다 현재 노드값의 최솟값이 1 크거나, 스택의 최솟값보다 현재 노드값의 최댓값이 1 작을때) 다음 반복을 시행한다.
스택을 pop한다
pop한 노드의 index를 정답으로 저장한다.
현재 노드의 최댓값과 최솟값을 업데이트한다
위 조건으로 돌아간다.
현재 노드를 스택에 삽입한다.
모든 순회가 끝났을 때, 스택에는 단 하나의 원소만이 남게 된다(가능한 경우밖에 주어지지 않으므로)