Which is Next
Time Limit: 1 Second Memory Limit: 32768 KB
Every computer science student knows binary trees. Here is one of many possible definitions of
binary trees. Binary trees are defined inductively. A binary tree t is either an external node (leaf) 
or an ordered pair 
representing an internal node 
with two subtrees attached, left subtree
and right subtree 
. Under this definition the number of nodes in any binary tree is odd. Given an
odd integer n let 
(n) denote the set of all binary trees with n nodes, both internal and external. For
instance 
(1) consists of only one tree 
, 
(3) = {
} and
(5) = {
, 
}. The trees of 
(5) are depicted in the figure below.
Denoted by |t| the number of nodes in a tree t. Given a tree t we define its unique integer identifier
(t) as follows:
(
) = 0
For instance, 
, 
, 
= 
.
Consider the following linear order on all binary trees:
In this order a single leaf 
is the smallest tree and given two nonleaf trees, the smaller one is that with
the smaller left tree, if the left subtrees are different, and that with the smaller right subtree, otherwise.
Hence for instance 
, since we have 
. Assume now that the trees in 
(n)
were sorted using the relater 
. Then, for each tree t in 
(n) we define the successor of t as the tree
that immediately follows t in 
(n). If t is the largest one in 
(n) then the successor of t is the smallest
tree in set 
(n). For instance, the successor of 
in 
(3) is the same tree 
and the successor of
in 
(5) is 
.
Given the integer identifier of some tree t can you give the identifier of the successor of t in 
(|t|)?
Write a program that:
- reads the identifier of some binary tree t,
- computes the identifier of the successor of t in
(|t|),
- writes the result.
Input
The input consists of several test cases.
For each case, there is one line contains one integer n (0 <= n <= 
) -- the identifier of some binary tree t.
Output
For each test case, print in one line an integer s -- the identifier of the successor of t in 
(|t|).
Sample Input
20
Sample Output
24Submit
Source: Central Europe 2003