Input
5 3 1 1 1 2 2 1 5 4 4 4 2 4 4 4 2 1 3 1 1
Output
0 1 1 2 0