Reverse Odd Segments

Given an array of integers, reverse each contiguous segment of odd numbers while keeping even numbers in their original positions. In other words, for every consecutive block of odd integers, the order of the block should be reversed. All even numbers remain unchanged.

For example, if the input array is [1, 3, 5, 2, 4, 7, 9], then the output should be [5, 3, 1, 2, 4, 9, 7] because the odd segment [1, 3, 5] is reversed to [5, 3, 1].

The operation can be defined mathematically as follows. Let \(a = [a_1, a_2, \ldots, a_n]\) be the input array. For every maximal consecutive subsequence \(a_i, a_{i+1}, \ldots, a_j\) such that \(a_k \equiv 1 \pmod{2}\) for all \(k = i, \ldots, j\), replace it with \(a_j, a_{j-1}, \ldots, a_i\). The even numbers remain in their original positions.

inputFormat

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

Print the modified array as a sequence of (n) space-separated integers on one line, where each contiguous segment of odd numbers is reversed.## sample

7
1 3 5 2 4 7 9

5 3 1 2 4 9 7