33848번 - 퍼시스턴트 스택

문제

퍼시스턴트를 아세요?

어떤 자료구조가 "퍼시스턴트(persistent)하다"는 것은 현재까지 자료의 상태 변화를 모두 보존하고 있다는 것이다. 이 문제에서 여러분들은 퍼시스턴트 스택을 구현해야 한다. 아래와 같은 쿼리를 수행하는 프로그램을 작성하시오.

• 1ドル$ $i$: 스택의 가장 위에 값 $i$를 집어넣는다.
• 2ドル$: 스택의 가장 위에 있는 값을 제거한다. 스택이 비어 있지 않은 경우에만 주어진다.
• 3ドル$ $j$: 최근 $j$개의 1ドル$번 또는 2ドル$번 쿼리를 취소한다. 취소할 수 있는 1ドル$번 또는 2ドル$번 쿼리가 $j$개 이상인 경우에만 주어진다.
• 4ドル$: 스택의 크기를 출력한다.
• 5ドル$: 스택의 가장 위에 있는 값을 출력한다. 만약 스택이 비어 있다면 대신 -1을 출력한다.

입력

첫 번째 줄에 쿼리의 개수를 나타내는 정수 $Q$가 주어진다. (1ドル \leq Q \leq 200,円 000$)

두 번째 줄부터 $Q$개의 줄에 걸쳐 한 줄에 하나씩 쿼리가 주어진다. (1ドル \leq i \leq 10^9;1 \leq j \leq Q$)

4ドル$번 또는 5ドル$번 쿼리는 한 번 이상 주어진다. 주어지는 모든 수는 정수이다.

출력

4ドル$번 또는 5ドル$번 쿼리가 주어질 때마다 쿼리의 답을 출력한다.

제한

힌트