Sort Odd Numbers in Array

You are given an array of integers. Your task is to sort only the odd numbers in ascending order while keeping the even numbers in their original positions. Formally, given an array \(a_1, a_2, \dots, a_n\), you need to create a new array \(b_1, b_2, \dots, b_n\) such that:

\(b_i =\) the \(k\)-th smallest odd number of the array if \(a_i\) is odd, and \(b_i = a_i\) otherwise.

If there are no odd numbers, the array should remain unchanged.

For example, if the input array is [5, 3, 2, 8, 1, 4], after sorting the odd numbers the output should be [1, 3, 2, 8, 5, 4].

inputFormat

The input is given via standard input (stdin) in the following format:

• The first line contains a single integer \(n\) representing the number of elements in the array.
• The second line contains \(n\) space-separated integers.

outputFormat

Output the modified array as a single line of \(n\) space-separated integers where odd numbers have been sorted in ascending order and even numbers remain in their original positions.

6
5 3 2 8 1 4

1 3 2 8 5 4