Inorder Traversal

Easyjavapythonccppjavascript

Given a binary tree, print its nodes in Left -> Root -> Right (inorder) order.

The tree is given in level order: M tokens, each an integer or null. The first token is the root; null marks a missing child. Children of a null are not listed.

Input Format

The first line contains an integer M, the number of level-order tokens. The second line contains M space-separated tokens (integers or null). It is blank when M is 0.

Output Format

Print the inorder traversal values separated by single spaces, or an empty line for an empty tree.

Example 1

Input

4
1 null 2 3

Output

1 3 2

Explanation: Visit the left subtree, then the root, then the right subtree.

Input (stdin)

Output

Run your code to see output here...