퍼시스턴트 스택

퍼시스턴트를 아세요?

어떤 자료구조가 "퍼시스턴트(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$번 쿼리가 주어질 때마다 쿼리의 답을 출력한다.