출구 앞의 주차권

문제

한 주차장에는 자동차 한 대가 지나갈 너비의 긴 주차 통로가 있다. 통로의 입구와 출구는 같은 쪽에 있고, 반대쪽 끝은 막혀 있다. 자동차는 들어온 순서대로 안쪽부터 자리를 채운다. 따라서 현재 주차된 자동차 중 가장 나중에 들어온 자동차만 다른 자동차를 움직이지 않고 바로 나갈 수 있다. 관리인은 입차할 때마다 자동차에 새로운 주차권 번호를 부여한다. 첫 번째로 입차한 자동차의 번호는 1이고, 이후 입차할 때마다 직전까지 발급한 가장 큰 번호보다 1 큰 번호를 부여한다. 이미 나간 자동차의 번호도 다시 사용하지 않는다. 주차 통로에는 이 문제의 모든 입차를 수용할 만큼 충분한 공간이 있으므로 입차가 거절되는 경우는 없다. 관리 기록에는 입차와 출차 요청이 시간순으로 적혀 있다. 기록 값이 0이면 새 자동차 한 대가 입차한다. 기록 값이 양수 x이면 주차권 번호가 x인 자동차가 출차를 요청한다. 이때 출구에서 가장 가까운 자동차의 번호가 x라면 그 자동차를 내보내고 요청을 성공으로 처리한다. 그렇지 않으면 요청을 실패로 처리하고 주차 상태를 그대로 유지한다. 실패한 요청을 처리하기 위해 다른 자동차를 잠시 밖으로 빼는 일은 하지 않는다. 또한 요청을 나중에 다시 처리하도록 보관하지도 않는다. 아직 발급하지 않은 번호, 이미 출차한 번호, 현재 다른 자동차에 가려져 있는 번호에 대한 요청은 모두 실패한다. 주차장이 비어 있을 때의 출차 요청도 실패한다. 처음에는 주차장이 비어 있다. 모든 기록을 순서대로 처리하여 각 출차 요청의 성공 여부와 마지막에 남아 있는 자동차 수를 구한다. 입차 기록 자체에 대해서는 성공 여부를 출력하지 않으며, 출차 요청의 결과는 요청이 나타난 순서대로 출력한다.

입력

첫째 줄에 기록 수를 나타내는 정수 Q가 주어진다. 1 ≤ Q ≤ 100,000이다.
둘째 줄에 기록 값 C_1, C_2, ..., C_Q가 공백으로 주어진다. 모든 i에 대해 C_i는 0 이상 Q 이하의 정수다. 0은 입차를, 양수는 해당 주차권 번호의 출차 요청을 나타낸다.

출력

각 출차 요청에 대해 성공하면 YES, 실패하면 NO를 한 줄에 하나씩 출력한다. 모든 요청의 결과를 출력한 뒤 마지막 줄에 남아 있는 자동차 수를 정수로 출력한다. 출차 요청이 하나도 없으면 남아 있는 자동차 수만 출력한다.

9
0 0 1 2 1 0 2 3 1

NO
YES
YES
NO
YES
NO
0

5
1 0 3 1 1

NO
NO
YES
NO
0

3
0 0 0

3

출처: Devin.KR 자체 제작