Challenge: nth Pre-order

Problem

Given a binary tree, print the value of nodes that will be at the $n^{th}$ index when the tree is traversed in pre-order.

Input

An integer index.

Output

Display the value of the node at the given index in pre-order traversal.

Sample input

index = 5

Sample output

9

Let’s look at the illustration below to better understand the problem.