P6182 [USACO10OPEN] Time Travel S

Farmer John bought a time machine, which allows him to manage his herd of cows conveniently. He now has $N$ operations ($1 \leq N \leq 8 \times 10^4$). Each operation is one of the following three types: 1. `a x`: Add a cow with ID $x$ ($1 \leq x \leq 10^6$). 2. `s`: Sell the most recently added cow (it is guaranteed that there is at least one cow at this time). 3. `t x`: Go back to the state **before the $x$-th operation** (it is guaranteed that the $x$-th operation exists). After Farmer John performs each operation, output the ID of the newest cow he currently owns. In particular, if he has no cows, output $-1$.

The first line contains an integer $N$. The next $N$ lines each describe one operation.

On the $i$-th line, output the ID of the newest cow Farmer John owns after the $i$-th operation. In particular, if he has no cows, output $-1$.

Below is the explanation for the sample, where the owned cows are already listed in the order they were added. | Operation No. | Operation | Owned Cows | Output | | ----------- | --------- | ---------- | ------ | | 1 | `a 5` | 5 | 5 | | 2 | `a 3` | 5,3 | 3 | | 3 | `a 7` | 5,3,7 | 7 | | 4 | `s` | 5,3 | 3 | | 5 | `t 2` | 5 | 5 | | 6 | `a 2` | 5,2 | 2 | | 7 | `t 4` | 5,3,7 | 7 | | 8 | `a 4` | 5,3,7,4 | 4 | | 9 | `s` | 5,3,7 | 7 | | 10 | `t 7` | 5,2 | 2 | | 11 | `s` | 5 | 5 | | 12 | `s` | / | -1 | Translated by ChatGPT 5