You process queries in order. In query , hire a new assassin numbered and choose an integer . If , assassin targets nobody. Otherwise, assassin targets the previously hired assassin .
After each query, assassin is dead if at least one living assassin targets . Otherwise, is alive. Thus, when an assassin who targets someone dies, their target may become alive again.
Find the number of living assassins after each query.
The input is given in the following format:
For each case, print the number of living assassins after each query, one per line.
Each case is given in the following format:
No additional constraints.