Rebuild BST from Inorder Traversal

You are given an array of integers representing the inorder traversal of a Binary Search Tree (BST). Your task is to reconstruct the BST in a balanced manner. The algorithm should select the middle element as the root and apply the same strategy recursively for the left and right subtrees.

After constructing the BST, perform an inorder traversal. Since the inorder traversal of a BST is always sorted, the output should match the input array.

Note: The input array will be sorted in increasing order.

inputFormat

The first line contains an integer n indicating the number of nodes in the BST.

The second line contains n space-separated integers in strictly increasing order which represent the inorder traversal of the BST.

outputFormat

Output a single line containing the inorder traversal of the reconstructed BST. The numbers should be printed in order and separated by a single space.

1
1

1