One day Hunter decides to skip the algorithm class to take a walk outside. While he’s strolling happily, he finds a permutation of N distinct positive integers 1…N on the ground.
Since the permutation is not sorted, Hunter decides to sort it using Hunter sort. (Sorted means in non-decreasing order.)
The Hunter sort is a recursive function:
HunterSort( L, R )
1. if the sub-array [L,R) is already sorted, return.
2. else let mid := floor( (L+R)/2 )
3. call HunterSort(L,mid)
4. call HunterSort(mid,R)
5. fuse the subarrays [L,mid) and [mid,R) into one sorted subarray
At first you need to call HunterSort(0,N). Note that the array is 0-indexed although its elements are 1…N.
After that he tries to sneak back into the algorithm class, but is caught on spot by Professor BFW. Hunter explains that he’s late because had to do K function calls to sort the permutation.
BFW does not quite believe him; having to do K function calls seems a bit outrageous. So he tells Hunter to construct a permutation of N distinct integers 1…N that requires exactly K function calls.
But he’s skipped too many algorithm classes to solve this problem, so he has come to you, a good student, for help.
(If you don't solve this, Hunter will come to your room in your sleep.)
The input has 1 line of two integers N and K, which is the size of permutation and how many function calls required to sort.
If such permutation does not exist and Hunter is lying, output -1, else output a permutation of 1…N that requires K function calls. If there are multiple answers, output any.