Question
The Binary Flip Challenge
Aryan and his friend Karan were discussing puzzles when Karan presented an intriguing challenge. He handed Aryan a binary array A of length N and asked, “Can you make this array as lexicographically small as possible?” The catch was that Aryan could perform an operation where he could choose two indices L and R, and if the segment A[L, R] contained an equal number of 1s and 0s, he could reverse that segment. Excited by the puzzle, Aryan quickly coded a solution. Can you solve it like Aryan?
Input
The first line of the input contains a single integer N denoting the length of an array.
The next line of the input contains N space-separated integers denoting the binary array A.
Constraints
1 ≤ N ≤ 105
0 ≤ A[i] ≤ 1
The next line of the input contains N space-separated integers denoting the binary array A.
Constraints
1 ≤ N ≤ 105
0 ≤ A[i] ≤ 1
Output
Print in a single line, lexicographically smallest possible N space-separated integers.
Example
Sample Input
5
0 1 1 0 0
Sample Output
0 0 0 1 1
Explanation
Rahul can choose L = 1 and R = 4, The chosen segment A[1, 4] = [1, 1, 0, 0], on reversing this we get [0, 0, 1, 1] hence the final array A becomes [0, 0, 0, 1, 1]. Note that this is the lexicographically smallest possible array.
5
0 1 1 0 0
Sample Output
0 0 0 1 1
Explanation
Rahul can choose L = 1 and R = 4, The chosen segment A[1, 4] = [1, 1, 0, 0], on reversing this we get [0, 0, 1, 1] hence the final array A becomes [0, 0, 0, 1, 1]. Note that this is the lexicographically smallest possible array.