Move Zeroes

You are given an array of integers. Your task is to move all zeroes in the array to the end while maintaining the relative order of the non-zero elements.

Instructions:

• The operation must be performed in-place, meaning you cannot use extra storage for another array.
• You only need to modify the given array.

Example:

Input:  [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

Note: If the array does not contain any zeroes, the output should be the same as the input. Similarly, if all elements are zeroes, the array remains unchanged.

Algorithm Hint: You can solve this problem using a two-pass algorithm. In the first pass, copy over the non-zero elements, and in the second pass, fill the rest of the array with zeroes.

The transformation of the array can be mathematically thought of as:

$$ A = [a_1, a_2, \ldots, a_n] \rightarrow A' = [b_1, b_2, \ldots, b_n]$$ where $$ b_i = \begin{cases} a_j & \text{if } a_j \neq 0 \text{ for some } j, \\ 0 & \text{otherwise.} \end{cases} $$

inputFormat

The first line of input contains an integer n representing the number of elements in the array.

The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output the modified array as n space-separated integers after moving all the zeroes to the end.

## sample

5
0 1 0 3 12

1 3 12 0 0