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.

Loading Editor...
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score