시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 22 12 12 57.143%

문제

모범생 현수는 코딩하는 시간을 늘리기 위해 타임 머신을 구매 했다. 현수는 정상적으로 문제를 코딩하거나 (타임 머신을 사용하지 않고), 과거의 임의의 지점으로 시간여행 할 수 있다.  미래로 시간 여행 할 수 없으며, 과거로 가면 새로운 미래가 진행된다.

현수는 자유롭게 문제를 풀거나 과거로 돌아가면서 자신이 푼 문제 목록을 기록한다. 과거로 돌아가면 과거 이전까지 풀었던 문제 목록만 남는다.

현수는  기록 되어 있는 문제 목록 중 가장 최근에 푼 문제 번호를 알고 싶다. (가장 최근에 푼 문제가 없다면 -1을 출력)

매 쿼리마다 문제 목록에 기록되어 있는 가장 최근에 푼 문제를 출력하는 프로그램을 작성하시오.

현수는 개인의 타임라인 관점에서 연속적인 업데이트를 나타내는  N (1 <= N <= 80,000) 개의 쿼리 Qi(1...N) 를 제공한다.

각 쿼리는 한 줄의 입력이다. 각 줄은 하나의 문자 c ( 'a', 's', 't' 중 하나)로 시작한다. c가 'a'또는 't' 이면 c 다음에 공백과 정수 K가 주어진다. (1 <= K <= 1,000,000)

c가 'a' 이면 현수는 문제 번호가 K인 문제를 풀고 문제 목록에 기록 한다.

c가 's' 이면 현수는 가장 최근에 작성한 문제 목록을 삭제한다.

c가 't'이면, 현수는 K 번째 쿼리 직전까지 시간을 거슬러 올라 간다. 즉, 현수는 K-1번째 쿼리와 K번째 쿼리 사이로 시간 여행한다. (입력을 위해 예제 입력 참조). K 쿼리  바로 전에 있던 푼 문제 목록으로 되돌아 간다.

이해를 돕기 위해 아래에 푼 문제 목록과 12개의 쿼리, 각 쿼리에 대한 출력결과가 주어진다.  

Q#   쿼리     문제목록      출력         참조
 1   a 5  -> [5]         => 5        5번 문제를 목록에 기록
 2   a 3  -> [5,3]       => 3        3번 문제를  목록에 기록
 3   a 7  -> [5,3,7]     => 7        7번 문제를 목록에 기록
 4   s    -> [5,3]       => 3        가장 최근 기록한 7를 목록에서 삭제
 5   t 2  -> [5]         => 5        2번째 쿼리 직전으로 되돌아감
 6   a 2  -> [5,2]       => 2        2번 문제를 목록에 기록
 7   t 4  -> [5,3,7]     => 7        4번째 쿼리 직전으로 되돌아감
 8   a 4  -> [5,3,7,4]   => 4        4번 문제를 목록에 기록
 9   s    -> [5,3,7]     => 7        가장 최근 기록한 4를 목록에서 삭제
10   t 7  -> [5,2]       => 2        7번째 쿼리 직전으로 되돌아감
11   s    -> [5]         => 5        가장 최근 기록한 2를 목록에서 삭제
12   s    -> []          => -1       가장 최근 기록한 5를 목록에서 삭제

입력

첫 번째 줄 : 하나의 정수 N

두번째 줄 부터 N+1번째 줄까지: 쿼리 Qi 

출력

1부터 N번째 줄 : Qi 처리 후 목록에 기록 되어 있는 가장 최근에 푼 문제를 출력하시오 (가장 최근에 푼 문제가 없으면 -1).

예제 입력

12
a 5
a 3
a 7
s
t 2
a 2
t 4
a 4
s
t 7
s
s

예제 출력

5
3
7
3
5
2
7
4
7
2
5
-1

힌트