Veronica Mars and the Binary Search Tree
With the help of Mac, Veronica Mars just came up with a new way of numbering Binary Search Tree(BST) nodes! She assigns the number to the root node, and any node indexed as will have a left child indexed as and a right child indexed as .
1
/ \
/ \
/ \
/ \
2 3
/ \ / \
/ \ / \
4 5 6 7
and so on...
Veronica tells this new numbering scheme to her dad, Keith, and and then inserts distinct numbers, , into a BST in increasing order of indices. Because he's better at hitting bad guys than hitting books, Keith promptly forgets the numbering scheme and asks for your help!
For each number , print the index of the node where it's located in the BST. See the Explanation section for more detail.
Input Format
The first line contains a single integer, , denoting the number of nodes in the tree.
The second line contains space-separated integers describing the respective integer elements, through .
Constraints
- for of the test cases.
- for of the test cases.
Output Format
Print a single line of space-separated integers where the number denotes the node index where number is present in the BST. As these numbers may be large, output them modulo .
Sample Input 0
4
5 3 6 2
Sample Output 0
1 2 3 4
Sample Input 1
3
1 2 3
Sample Output 1
1 3 7
Explanation
Sample Case 0:
The BST formed is:
5(1)
/ \
/ \
3(2) 6(3)
/
2(4)
* The node indices are written in parentheses.
Sample Case 1:
The BST formed is
1(1)
\
\
2(3)
\
\
3(7)
* The node indices are written in parentheses.