Sort Odd Numbers in a List

You are given a list of integers. Your task is to sort only the odd numbers in the list in ascending order while leaving the even numbers in their original positions.

More formally, let \(a_1,a_2,\ldots,a_n\) be the sequence of integers. Define a new sequence \(b_1,b_2,\ldots,b_n\) such that for every \(i\) (\(1 \le i \le n\)):

• If \(a_i\) is even, then \(b_i = a_i\).
• If \(a_i\) is odd, then \(b_i\) is the next smallest odd number from the sorted order of all odd numbers in \(a\).

For example, for the list [5, 3, 2, 8, 1, 4], the odd numbers are [5, 3, 1]. Sorting them gives [1, 3, 5]. Placing them back in the positions of the odd numbers results in [1, 3, 2, 8, 5, 4].

inputFormat

The input is read from standard input. The first line contains a non-negative integer \(n\) representing the number of elements in the list. The second line contains \(n\) space-separated integers.

outputFormat

Print the modified list to standard output as a sequence of space-separated integers, preserving the order of even numbers and replacing odd numbers with their sorted order.

6
5 3 2 8 1 4

1 3 2 8 5 4