Just an alert:

Are you aware that there are multiple solutions, e.g.:
from the sample input:

Input:

4
1011

Output 1:

1001

Output 2:

1111

My issue is that you don't mention anything about this in
the problem definition -- i.e. is any of the possible
solutions valid?