Binary Parity Tree Inorder Traversal

Given a list of integers, construct a Binary Parity Tree (BPT) following these rules:

• All even numbers are inserted into the left subtree.
• All odd numbers are inserted into the right subtree.
• The first element (root) is always considered even.

After constructing the BPT, perform an inorder traversal defined as:

$$\text{inorder}(node) = [node.value] \Vert \text{inorder}(node.left) \Vert \text{inorder}(node.right)$$

and output the sequence of visited node values as space-separated integers.

inputFormat

The first line contains an integer n representing the number of elements. The second line contains n space-separated integers.

outputFormat

Output a single line with the inorder traversal of the Binary Parity Tree as space-separated integers.

## sample

5
2 3 4 1 5

2 4 3 1 5

</p>