{"problem":{"name":"D. Merge Sort","description":{"content":"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 alr","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF873D"},"statements":[{"statement_type":"Markdown","content":"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:\n\n1.  If the segment \\[_l_, _r_) is already sorted in non-descending order (that is, for any _i_ such that _l_ ≤ _i_ < _r_ - 1 _a_\\[_i_\\] ≤ _a_\\[_i_ + 1\\]), then end the function call;\n2.  Let ;\n3.  Call _mergesort_(_a_, _l_, _mid_);\n4.  Call _mergesort_(_a_, _mid_, _r_);\n5.  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.\n\nThe array in this problem is 0\\-indexed, so to sort the whole array, you need to call _mergesort_(_a_, 0, _n_).\n\nThe 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.\n\nIvan 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_.\n\nHelp Ivan to find an array he wants!\n\n## Input\n\nThe 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.\n\n## Output\n\nIf 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.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"归并排序是一种著名的排序算法。用于对数组 #cf_span[a] 中下标在 #cf_span[[l, r) 范围内的元素进行排序的主函数可以如下实现：\n\n本题中的数组是 #cf_span[0]-索引的，因此要对整个数组排序，你需要调用 #cf_span[mergesort(a, 0, n)]。\n\n函数 #cf_span[mergesort] 的调用次数非常重要，因此 Ivan 决定在排序过程中统计该次数。例如，如果 #cf_span[a = {1, 2, 3, 4}]，则只会发生 #cf_span[1] 次 #cf_span[mergesort] 调用——即 #cf_span[mergesort(0, 4)]，它会检查数组是否已排序，然后结束。如果 #cf_span[a = {2, 1, 3}]，则调用次数为 #cf_span[3]：首先调用 #cf_span[mergesort(0, 3)]，它将设置 #cf_span[mid = 1] 并调用 #cf_span[mergesort(0, 1)] 和 #cf_span[mergesort(1, 3)]，而这两个调用不会进行任何递归调用，因为区间 #cf_span[(0, 1)] 和 #cf_span[(1, 3)] 已经有序。\n\nIvan 实现了一个统计 #cf_span[mergesort] 调用次数的程序，但现在他需要测试它。为此，他需要找到一个数组 #cf_span[a]，使得 #cf_span[a] 是一个大小为 #cf_span[n] 的排列（即，#cf_span[a] 中的元素个数为 #cf_span[n]，且区间 #cf_span[[1, n]] 中的每个整数都恰好出现一次），并且在对该数组进行排序时，#cf_span[mergesort] 的调用次数恰好为 #cf_span[k]。\n\n请帮助 Ivan 找到他想要的数组！\n\n第一行包含两个数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 100000]，#cf_span[1 ≤ k ≤ 200000]）——所需排列的大小和排序时所需的 #cf_span[mergesort] 调用次数。\n\n如果不存在一个大小为 #cf_span[n] 的排列，使得排序时恰好发生 #cf_span[k] 次 #cf_span[mergesort] 调用，则输出 #cf_span[ - 1]。否则，请输出 #cf_span[n] 个整数 #cf_span[a[0], a[1], ..., a[n - 1]]——满足条件的排列的元素。如果有多个答案，输出任意一个即可。\n\n## Input\n\n第一行包含两个数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 100000]，#cf_span[1 ≤ k ≤ 200000]）——所需排列的大小和排序时所需的 #cf_span[mergesort] 调用次数。\n\n## Output\n\n如果不存在一个大小为 #cf_span[n] 的排列，使得排序时恰好发生 #cf_span[k] 次 #cf_span[mergesort] 调用，则输出 #cf_span[ - 1]。否则，请输出 #cf_span[n] 个整数 #cf_span[a[0], a[1], ..., a[n - 1]]——满足条件的排列的元素。如果有多个答案，输出任意一个即可。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 100000 $, $ 1 \\leq k \\leq 200000 $.  \nLet $ a = (a_0, a_1, \\dots, a_{n-1}) $ be a permutation of $ \\{1, 2, \\dots, n\\} $.  \n\n**Constraints**  \nThe number of calls to `mergesort(l, r)` during the execution of `mergesort(a, 0, n)` must equal $ k $.  \nEach call `mergesort(l, r)` with $ r - l > 1 $ triggers two recursive calls: `mergesort(l, mid)` and `mergesort(mid, r)`, where $ \\text{mid} = \\lfloor (l + r)/2 \\rfloor $.  \nA call `mergesort(l, r)` is counted if $ r - l \\geq 1 $.  \nThe total number of calls equals the number of nodes in the recursion tree rooted at $ (0, n) $, where each internal node (with $ r - l > 1 $) has two children, and leaves correspond to intervals of length $ \\leq 1 $.  \n\n**Objective**  \nFind a permutation $ a $ of $ \\{1, 2, \\dots, n\\} $ such that the recursion tree of `mergesort(a, 0, n)` has exactly $ k $ nodes.  \nIf no such permutation exists, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF873D","tags":["constructive algorithms","divide and conquer"],"sample_group":[["3 3","2 1 3"],["4 1","1 2 3 4"],["5 6","\\-1"]],"created_at":"2026-03-03 11:00:39"}}