Balanced Binary Search Tree Construction

Given a sorted array of unique integers, construct a height-balanced binary search tree (BST). A BST is a binary tree where for each node, all values in the left subtree are less than the node’s value and all values in the right subtree are greater. A height-balanced tree is defined as a binary tree in which the difference in heights of the left and right subtrees is at most 1. The in-order traversal of a BST built from a sorted array will return the original array.

To ensure that the tree is balanced, you should choose the middle element of the array as the root and recursively build the left and right subtrees. Mathematically, the balanced condition for any node is:

[ |h_{left} - h_{right}| \leq 1 ]

Read the input from stdin and print the resulting in-order traversal to stdout.

inputFormat

The first line contains a single integer n (1 \le n \le 10⁵), the number of elements in the array. The second line contains n space-separated integers sorted in ascending order.

outputFormat

Print the in-order traversal of the constructed BST. The output should be the n integers separated by a single space. (Note: An in-order traversal of a BST constructed from a sorted array returns the original array.)

5
-10 -3 0 5 9

-10 -3 0 5 9