Input
6 3 1 2 3 5 2 1 4 3 5 6 6 1 4 2 5 3 1 1 6 3 2 1 6 5 4 5 3 1 5 2 4
Output
3 3 1 1 2 1