When Taeho isn't busy working on crazy crypto research in his DSP lab, he is most likely thinking of devious ways of destroying the students in algorithms. For example, he recently came up with the following challenge:

Given a sequence of integers in ascending order, create a minimal binary search tree (that is, the tree has the minimum necessary height) and display all the nodes in the tree level by level.

Since most of his students have already taken Data Structures, they immediately suggested an approach that involves reading the sequence of integers and inserting into a binary search tree. Once the BST is constructed, it could be printed out by using a simple traversal.

Taeho smirked at this suggestion and politely said that while this works, it runs in `O(nlogn)` time... and that there is a better approach that utilizes divide and conquer to run in `O(N)` time.

You are to implement this more efficient version.

## Input¶

You will be given a series of lines, where each line contain a sequence of integers in ascending order:

### Example Input¶

``````0 1 2 3 4 5 6
``````

## Output¶

For each sequence of integers, you are to output the binary search tree constructed from the sequence of integers by displaying all the nodes in the BST level by level:

### Example Output¶

``````3
1 5
0 2 4 6
``````

#### Algorithmic Complexity¶

For each input test case, your solution should have the following targets:

 Time Complexity `O(N)`, where `N` is the number of nodes in each BST. Space Complexity `O(N)`, where `N` is the number of nodes in each BST.

Your solution may be below the targets, but it should not exceed them.

## Submission¶

``````\$ cd path/to/cse-30872-su24-assignments     # Go to assignments repository
\$ git checkout master                       # Make sure we are on master
\$ git pull --rebase                         # Pull any changes from GitHub

\$ git checkout -b challenge13               # Create and checkout challenge13 branch

\$ \$EDITOR challenge13/program.cpp           # Edit your code

\$ git commit -m "challenge13: done"         # Commit your changes

\$ git push -u origin challenge13            # Send changes to GitHub
``````

To check your code, you can use the `.scripts/check.py` script or curl:

``````\$ .scripts/check.py
Checking challenge13 program.cpp ...
Result Success
Time 0.57
Score 6.00 / 6.00

\$ curl -F source=@challenge13/program.cpp https://dredd.h4x0r.space/code/cse-30872-su24/challenge13
{"result": "Success", "score": 6, "time": 0.5650837421417236, "value": 6, "status": 0}
``````

#### Pull Request¶

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the instructor.