Sort Array By Parity

easy

1. Given an array nums of non-negative integers.
2. Arrange elements of array in specific order, all even elements followed by odd elements. [even -&gt; odd]
3. Preserve the order of Even elements without using extra space.
4. Hence question is order specific so you have to match your output in order of given output.

Input Format

7 9 3 8 7 6 2 3

Output Format

8 6 2 7 3 9 3 Explanation : {even -> odd}, 8 is before 6 in given input as well as in output, same for 6,2.

Constraints

1. 1 &lt;= nums.length &lt;= 5000
2. 0 &lt;= nums[i] &lt;= 5000

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

7
9 3 8 7 6 2 3

Output

8 6 2 7 3 9 3

Search In Rotated Sorted Array

Find Minimum In Rotated Sorted Array