Convert Sorted Array to Balanced BST

You are given a sorted array of n integers in non-decreasing order. Your task is to convert the sorted array into a height-balanced binary search tree (BST).

A BST is height-balanced if the depth of the two subtrees of every node never differ by more than one. The conversion should follow a divide and conquer approach by choosing the middle element as the root. In fact, the index for the root is computed as \(\lfloor(l+r)/2\rfloor\) for the current subarray.

After building the BST, perform a level-order traversal (breadth-first search) of the tree and output the values of the nodes. If a node is missing (i.e. a null child), output "null" in its place. Trailing "null" values should be omitted in the final output.

inputFormat

The input is given via stdin and has the following format:

• The first line contains an integer \(n\) representing the number of elements in the sorted array.
• If \(n > 0\), the second line contains \(n\) space-separated integers sorted in non-decreasing order.

outputFormat

Output the level-order traversal of the height-balanced BST to stdout in one line. The values are separated by a single space and missing nodes are represented by the string "null". Do not print any trailing "null" values.

## sample

5
-10 -3 0 5 9

0 -10 5 null -3 null 9