Parity Index Arrangement

The first line of input contains an integer 'n', the size of the array.

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

Print 'n' space-separated integers representing the rearranged array.

The solution must be in-place, meaning you should not use any extra array. The required auxiliary space is O(1).

The size of the array 'n' will always be an even number.

There can be multiple correct outputs; your solution needs to produce any one of them.

Sample Input 1:

6
3 6 12 1 5 8

Sample Output 1:

6 3 12 1 8 5

Explanation for Sample 1:

In the final array `[6, 3, 12, 1, 8, 5]`:
At even indices (0, 2, 4): We have `6, 12, 8` (all even).
At odd indices (1, 3, 5): We have `3, 1, 5` (all odd).
The condition is satisfied.

Sample Input 2:

10
10 9 7 18 13 19 4 20 21 14

Sample Output 2:

10 9 18 7 20 19 4 13 14 21

Explanation for Sample 2:

The initial array `[10, 9, ...]` has `10` (even) at index 0 (even) and `9` (odd) at index 1 (odd).
The algorithm finds the first misplaced odd number at an even index (7 at index 2) and the first misplaced even number at an odd index (18 at index 3). It swaps them.
The process continues until all elements are in their correct parity-indexed positions.

Expected Time Complexity:

The expected time complexity is O(n).

Constraints:

2 <= n <= 10^5
'n' is always even.
1 <= arr[i] <= 10^9

Time limit: 1 sec