Parity Index Arrangement

You are given an array 'arr' of size 'n'. The array is guaranteed to contain an equal number of even and odd integers.

Your task is to rearrange the elements of the array in-place such that every even number is at an even index (0, 2, 4, ...) and every odd number is at an odd index (1, 3, 5, ...).

Input Format:

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'.

Output Format:

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

Note:

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.