← 返回题目列表

Codeforces · 873/D

D. 合并排序

中文机器翻译题面 查看原题

归并排序是一种众所周知的排序算法。使用 [l, r) 中的索引对数组 a 的元素进行排序的主函数可以实现如下:

1. 如果段 [l, r) 已按非降序排序(即,对于任意 i,且 l ≤ i < r - 1 a[i] ≤ a[i + 1]),则结束函数调用;
2. 令 $$mid = \left\lfloor \frac{l+r}{2} \right\rfloor$$;
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 已经实现了计算归并排序调用次数的程序,但现在他需要测试它。为此,他需要找到一个数组 a,使得 a 是大小为 n 的排列(即 a 中的元素数量为 n,并且 [1, n] 中的每个整数都可以在该数组中找到),并且在对数组进行排序时调用归并排序的次数恰好是 k。

帮助Ivan找到他想要的数组!

输入

第一行包含两个数字 n 和 k (1 ≤ n ≤ 100000, 1 ≤ k ≤ 200000) — 所需排列的大小以及对其进行排序所需的归并排序调用次数。

输出

如果大小为 n 的排列不存在,使得在排序时恰好有 k 次归并排序调用,则输出 - 1。否则输出 n 个整数 a[0], a[1], ..., a[n - 1] — 满足所需条件的排列的元素。如果有多个答案,请打印其中任何一个。

示例

输入 #1

3 3

输出 #1

2 1 3

输入 #2

4 1

输出 #2

1 2 3 4

输入 #3

5 6

输出 #3

-1