Sorted Array to Balanced BST

Given a sorted array of integers, your task is to convert it into a height-balanced binary search tree (BST) and then output its pre-order traversal.

A BST is height-balanced if for every node, the height difference between its left and right subtrees is at most 1, i.e., \[ |h(left) - h(right)| \le 1 \]

The resulting tree will be used to perform a pre-order traversal (visit the root, then left subtree, and finally right subtree) and output the node values separated by spaces.

If the input array is empty, output nothing.

inputFormat

The input consists of two parts:

1. The first line contains an integer n, the number of elements in the array.
2. If n > 0, the second line contains n space-separated integers in ascending order. If n == 0, there is no second line.

outputFormat

Output a single line that contains the pre-order traversal of the BST as space-separated integers. If the tree is empty, output nothing.

5
-10 -3 0 5 9

0 -10 -3 5 9