Merge Sort

题意翻译

归并排序是有名的排序算法。对数组$a$的元素进行排序的主要功能可以按如下步骤实现： 1. 如果$[l,r)$区间已经以非降序排列时（即对于任意$i$满足$l<=i<r-1$,都有$a[i]<=a[i+1])$,这时结束函数调用； 2. 令$mid=[(l+r)/2]$; 3. 调用$mergesort(a,l,mid)$; 4. 调用$mergesort(a,mid,r)$; 5. 合并$[l,mid),[mid,r)$区间，使$[l,r)$按非降序排列。合并算法不会调用任何其他函数。 题中数组索引从0开始，因此对整个数组进行排序需调用$mergesort(a,0,n)$。 函数$mergesort$的调用次数非常重要，因此Ivan决定在对数组进行排序时对其进行计算。例如，如果$a=1,2,3,4$，那么就会有1次$mergesort$调用—— $mergesort(0,4)$，其检查到数组已排好序并结束程序。如果$a=2,1,3$，则调用次数为3：首先，调用$mergesort(0,3)$，然后设$mid=1$，调用$mergesort(0,1)$和$mergesort(1,3)$，此后不执行任何递归调用，因为$(0,1)$和$(1,3)$已经排好序。 Ivan已经实现了计算$mergesort$调用次数的程序，但现在他需要测试这个程序。为此，他需要找到一个长度为$n$的序列$a$（即$a$中的元素数是$n$，且这个数组包含$[1,n]$中的每个整数），并且在排序数组时$mergesort$调用的次数正好是$k$。 请帮Ivan找到他想要的序列！ # **输入输出格式**# **输入格式：** 第一行包含两个数字$n$和$k$ _$(1<=n<=100000,1<=k<=200000)$_ ——即所需序列的长度和对该序列排序需要调用$mergesort$的次数。 **输出格式：** 如果不存在排序时正好调用$k$次$mergesort$且长度为$n$的序列，则输出−1。否则输出$n$个整数$a[0],a[1],...,a[n-1]$——即符合要求的序列的各个元素。如果有多个答案，输出其中任意一个。

题目描述

Merge sort is a well-known sorting algorithm. The main function that sorts the elements of array $ a $ with indices from $ [l,r) $ can be implemented as follows: 1. If the segment $ [l,r) $ is already sorted in non-descending order (that is, for any $ i $ such that $ l<=i&lt;r-1 $ $ a[i]<=a[i+1] $ ), then end the function call; 2. Let ; 3. Call $ mergesort(a,l,mid) $ ; 4. Call $ mergesort(a,mid,r) $ ; 5. Merge segments $ [l,mid) $ and $ [mid,r) $ , making the segment $ [l,r) $ sorted in non-descending order. The merge algorithm doesn't call any other functions. The array in this problem is $ 0 $ -indexed, so to sort the whole array, you need to call $ mergesort(a,0,n) $ . The number of calls of function $ mergesort $ is very important, so Ivan has decided to calculate it while sorting the array. For example, if $ a={1,2,3,4} $ , then there will be $ 1 $ call of $ mergesort $ — $ mergesort(0,4) $ , which will check that the array is sorted and then end. If $ a={2,1,3} $ , then the number of calls is $ 3 $ : first of all, you call $ mergesort(0,3) $ , which then sets $ mid=1 $ and calls $ mergesort(0,1) $ and $ mergesort(1,3) $ , which do not perform any recursive calls because segments $ (0,1) $ and $ (1,3) $ are sorted. Ivan has implemented the program that counts the number of $ mergesort $ calls, but now he needs to test it. To do this, he needs to find an array $ a $ such that $ a $ is a permutation of size $ n $ (that is, the number of elements in $ a $ is $ n $ , and every integer number from $ [1,n] $ can be found in this array), and the number of $ mergesort $ calls when sorting the array is exactly $ k $ . Help Ivan to find an array he wants!

输入输出格式

输入格式

The first line contains two numbers $ n $ and $ k $ ( $ 1<=n<=100000 $ , $ 1<=k<=200000 $ ) — the size of a desired permutation and the number of $ mergesort $ calls required to sort it.

输出格式

If a permutation of size $ n $ such that there will be exactly $ k $ calls of $ mergesort $ while sorting it doesn't exist, output $ -1 $ . Otherwise output $ n $ integer numbers $ a[0],a[1],...,a[n-1] $ — the elements of a permutation that would meet the required conditions. If there are multiple answers, print any of them.

输入输出样例

输入样例 #1

3 3

输出样例 #1

2 1 3 

输入样例 #2

4 1

输出样例 #2

1 2 3 4 

输入样例 #3

5 6

输出样例 #3

-1