Balanced Binary Search Tree Inorder Traversal

You are given an unsorted array of integers. Your task is to construct a balanced binary search tree (BST) from the array and then perform an inorder traversal of the BST. The BST must be constructed by first sorting the array and then using a recursive approach to pick the middle element to ensure that the tree remains balanced. In other words, if you have an array ( nums ) of length ( n ), choose the middle index ( mid = \lfloor n/2 \rfloor ) as the root, and then recursively do this for the left and right halves of the array.

The final output should be the inorder traversal of the BST. Note that an inorder traversal of a BST returns the elements in non-decreasing order, so the result will be the sorted array (including duplicates).

inputFormat

The first line contains an integer ( n ) representing the number of elements in the array. The second line contains ( n ) space-separated integers.

outputFormat

Output a single line containing the inorder traversal of the constructed balanced BST. The numbers should be space-separated.## sample

7
3 1 4 1 5 9 2

1 1 2 3 4 5 9