Balanced Binary Search Tree

Given an unbalanced binary search tree (BST), your task is to convert it into a balanced BST containing the same set of nodes. A balanced BST is defined as a binary tree in which the heights of the two subtrees of any node differ by no more than one. The BST is initially constructed by inserting nodes in a given order. After balancing the BST, output the in-order traversal of the balanced BST (which is the sorted order of the node values).

The rebalancing should preserve the binary search tree property. Use an efficient algorithm to ensure that the tree is balanced.

inputFormat

The first line contains a single integer (N) ((1 \leq N \leq 10^5)), representing the number of nodes in the BST. The second line contains (N) distinct integers separated by spaces which are inserted into the BST in the given order.

outputFormat

Output a single line containing the in-order traversal of the balanced BST. The node values should be output in a single line separated by a single space.## sample

6
30 20 40 10 25 50

10 20 25 30 40 50