1020 - Sequence

Time Limit: 4s Memory Limit: 128MB

Submissions: 210 Solved: 22
Description
You must have known the sequence define as follows: a[1]=1; for every i=1,2,3,... a[2*i]=a[i]; a[2*i+1]=a[i]+a[i+1]; You can easily prove that every postive number will appear in this sequence. Now give you a postive number n,your task is to determine the first position n appears.
Input
Only one number n (0<n<400000).
Output
The first position n appears.The answer won't exceed 263-1
Sample Input
1
2
3
4
Sample Output
1
3
5
9
Hint
64位整型数,用long long定义,输出用%lld。
Source
cjq