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:  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;  Let $\operatorname{mid} = \lfloor \frac{l + r}{2} \rfloor$;  Call mergesort(a, l, mid);  Call mergesort(a, mid, r);  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!


-----Input-----

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.


-----Output-----

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.


-----Examples-----
Input
3 3

Output
2 1 3 
Input
4 1

Output
1 2 3 4 
Input
5 6

Output
-1

Difficulty: MEDIUM_HARD
Tags: Divide and conquer

Constructive algorithms

Starter code:

Solutions:
def unsort(arr, left, right, k):
	if k[0] <= 0 or left >= right - 1:
		return
	k[0] -= 2
	mid = (left + right) // 2
	(arr[mid], arr[mid - 1]) = (arr[mid - 1], arr[mid])
	unsort(arr, left, mid, k)
	unsort(arr, mid, right, k)
(n, k) = map(int, input().split())
if k % 2 == 0:
	print(-1)
else:
	k = [k - 1]
	arr = [i for i in range(1, n + 1)]
	unsort(arr, 0, n, k)
	if not k[0]:
		print(*arr)
	else:
		print(-1)


def unsort(d, left, right, k):
	if k[0] <= 0 or left >= right - 1:
		return
	k[0] -= 2
	mid = (left + right) // 2
	tmp = d[mid - 1]
	d[mid - 1] = d[mid]
	d[mid] = tmp
	unsort(d, left, mid, k)
	unsort(d, mid, right, k)

def main():
	k = [0]
	(n, k[0]) = (int(i) for i in input().split())
	if k[0] % 2 == 0:
		print('-1')
		return
	d = [i for i in range(n + 1)]
	k[0] -= 1
	unsort(d, 1, n + 1, k)
	if k[0] == 0:
		print(*d[1:])
	else:
		print('-1')

def __starting_point():
	main()
__starting_point()


k1 = 0

def main():
	(n, k) = [int(x) for x in input().split()]
	if k & 1 == 0 or k > 2 * n - 1:
		print('-1')
	else:
		lst = [0] * n
		nonlocal k1
		k1 = k - 1

		def fill_arr(l, r, val):
			nonlocal k1
			if r <= l + 1:
				lst[l] = val
			elif k1 == 0:
				for i in range(l, r):
					lst[i] = val + i - l
			else:
				k1 -= 2
				m = (l + r) // 2
				fill_arr(l, m, val + r - m)
				fill_arr(m, r, val)
		fill_arr(0, n, 1)
		print(' '.join([str(x) for x in lst]))

def __starting_point():
	main()
__starting_point()


import os
import sys
import copy
num = 0
a = None
k = None

def solve():
	global k, a
	(n, k) = map(lambda x: int(x), input().split())
	savek = copy.deepcopy(k)
	a = [_ + 1 for _ in range(n)]

	def mgsort(l, r):
		global num, a, k
		mid = l + r >> 1
		if r - l == 1 or k == 1:
			return
		k -= 2
		(a[l:mid], a[mid:r]) = (a[mid:r], a[l:mid])
		mgsort(l, mid)
		mgsort(mid, r)
	if k % 2 != 0:
		mgsort(0, n)
	if k == 1:
		for i in a:
			print(i, sep=' ', end=' ')
	else:
		print(-1)
solve()


import sys, math, queue, bisect
MOD = 10 ** 9 + 7
sys.setrecursionlimit(1000000)
(n, k) = list(map(int, input().split()))
k -= 1
a = [-1 for i in range(n)]
c = 1

def merge(l, r, k):
	nonlocal a, c
	if l >= r or k % 2 != 0:
		return False
	if k == 0:
		for i in range(l, r):
			a[i] = c
			c += 1
		return True
	k -= 2
	m = (l + r) // 2
	if k // 2 % 2 == 0:
		if merge(m, r, k // 2):
			return merge(l, m, k // 2)
		else:
			return False
	elif merge(m, r, k // 2 + 1):
		return merge(l, m, k // 2 - 1)
	else:
		return False
if not merge(0, n, k):
	print(-1)
	return
print(*a)


(n, k) = map(int, input().split())
if k % 2 == 0:
	print(-1)
	return ()
k -= 1
a = [i + 1 for i in range(n)]

def sl(l, r):
	nonlocal k
	if r - l < 2 or k == 0:
		return
	k -= 2
	m = (l + r) // 2
	(a[m], a[m - 1]) = (a[m - 1], a[m])
	sl(l, m)
	sl(m, r)
sl(0, n)
if k != 0:
	print(-1)
	return ()
print(' '.join([str(i) for i in a]))


(n, m) = list(map(int, input().split()))
res = []

def solve(begin, end, rem):
	if rem < 2:
		res.extend(list(range(begin, end)))
		return rem
	if end - begin == 1:
		res.append(begin)
		return rem
	rem -= 2
	mid = (begin + end + 1) // 2
	rem = solve(mid, end, rem)
	rem = solve(begin, mid, rem)
	return rem
rem = solve(1, n + 1, m - 1)
if rem == 0:
	print(' '.join(map(str, res)))
else:
	print(-1)


def arr(n, k, l):
	global flag
	if k == 0:
		return list(range(l, l + n))
	if n == 1:
		flag = True
		return [0]
	if k % 4 == 2:
		k1 = k2 = k // 2 - 1
	else:
		k1 = (k - 4) // 2
		k2 = k1 + 2
	n1 = n // 2
	n2 = n - n1
	a1 = arr(n1, k1, l + n2)
	a2 = arr(n2, k2, l)
	a1.extend(a2)
	return a1
(n, k) = [int(i) for i in input().split()]
flag = False
ans = arr(n, k - 1, 1)
if k % 2 == 0:
	flag = True
if flag:
	print(-1)
else:
	for i in ans:
		print(i, end=' ')


(size, call_no) = map(int, input().split())
list_val = [i for i in range(1, size + 1)]

def modify(list_val, l, r):
	global count
	if count == call_no or r - l < 2:
		return
	mid = (l + r) // 2
	(list_val[mid - 1], list_val[mid]) = (list_val[mid], list_val[mid - 1])
	count += 2
	modify(list_val, l, mid)
	modify(list_val, mid, r)
if call_no == 1:
	str_val = ' '.join(map(str, list_val))
	print(str_val)
elif call_no % 2 == 0:
	print('-1')
else:
	count = 1
	modify(list_val, 0, len(list_val))
	if count < call_no:
		print('-1')
	else:
		print(' '.join(map(str, list_val)))


from sys import stdin, stdout
(n, k) = map(int, stdin.readline().split())
value = n
cnt = k
ans = []

def generate(l, r):
	global cnt, value
	if l == r:
		ans.append(value)
		value -= 1
		return 0
	if not cnt:
		for i in range(value - (r - l), value + 1):
			ans.append(i)
		value -= r - l + 1
		return 0
	cnt -= 2
	middle = l + r + 1 >> 1
	generate(l, middle - 1)
	generate(middle, r)
cnt -= 1
generate(0, n - 1)
if len(ans) != n or cnt:
	stdout.write('-1')
else:
	stdout.write(' '.join(list(map(str, ans))))


(n, k) = map(int, input().split())
a = [i + 1 for i in range(n)]
if not k & 1:
	print(-1)
	return ()
k -= 1

def f(l, r):
	nonlocal k
	if k < 2 or r - l < 2:
		return
	k -= 2
	m = (l + r) // 2
	(a[m - 1], a[m]) = (a[m], a[m - 1])
	f(l, m)
	f(m, r)
f(0, n)
if not k == 0:
	print(-1)
	return ()
for i in a:
	print(int(i), end=' ')


import sys
(n, k) = map(int, input().split())
k = [k - 1]
ans = [-1] * n

def set_n(l, r, rev, cur):
	if not rev:
		for i in range(l, r):
			ans[i] = cur
			cur += 1
	else:
		for i in range(r - 1, l - 1, -1):
			ans[i] = cur
			cur += 1
	return cur

def rec(l, r, cur):
	if r - l == 1:
		set_n(l, r, 0, cur)
		return
	if k[0] < 2:
		set_n(l, r, 0, cur)
		return
	k[0] -= 2
	mid = l + r >> 1
	rec(mid, r, cur)
	rec(l, mid, cur + (r - mid))
rec(0, n, 1)
if k[0] != 0:
	print(-1)
else:
	print(*ans)


import sys

def cal(l, r):
	global k
	if r - l < 2 or k == 0:
		return
	k -= 2
	m = (l + r) // 2
	(a[m], a[m - 1]) = (a[m - 1], a[m])
	cal(l, m)
	cal(m, r)
(n, k) = map(int, sys.stdin.readline().split())
if k % 2 == 0:
	sys.stdout.write('-1')
else:
	k -= 1
	a = [i + 1 for i in range(n)]
	cal(0, n)
	if k != 0:
		sys.stdout.write('-1')
	else:
		sys.stdout.write(' '.join([str(i) for i in a]))


def create_list(n, num_of_calls):
	if n == 1:
		return ([1], 0)
	if n == 2:
		return ([2, 1], 2)
	if num_of_calls == 2:
		return (list(range(2, n // 2 + 2)) + [1] + list(range(n // 2 + 2, n + 1)), 2)
	(list1, num_of_calls1) = create_list(n // 2, num_of_calls - 2)
	if num_of_calls1 == num_of_calls - 2:
		return (list1 + list(range(n // 2 + 1, n + 1)), num_of_calls)
	(list2, num_of_calls2) = create_list((n + 1) // 2, num_of_calls - num_of_calls1 - 2)
	return (list1 + [x + n // 2 for x in list2], num_of_calls1 + num_of_calls2 + 2)

def main():
	(n, k) = [int(x) for x in input().split()]
	if k % 2 != 1:
		print(-1)
		return
	if k == 1:
		print(' '.join([str(x) for x in range(1, n + 1)]))
		return
	(num_list, num_of_calls) = create_list(n, k - 1)
	if num_of_calls != k - 1:
		print(-1)
		return
	print(' '.join([str(x) for x in num_list]))

def __starting_point():
	main()
__starting_point()


from sys import stdin, stdout

def solve(l, r, nl, nr, target):
	if r - l < 2:
		if target:
			print(-1)
			exit()
		if l != r:
			ans[l] = nl
		return
	k = target // 2
	y = target % 2
	m = (l + r) // 2
	nm = (nl + nr) // 2
	if y:
		print(-1)
		exit()
	elif k == 1:
		if nm - nr != l - m:
			nm = l - m + nr
		solve(l, m, nm, nr, k - 1)
		solve(m, r, nl, nm, k - 1)
	elif k:
		if k % 2:
			solve(l, m, nl, nm, k - 1)
			solve(m, r, nm, nr, k - 1)
		else:
			solve(l, m, nl, nm, k - 2)
			solve(m, r, nm, nr, k)
	else:
		for i in range(l, r):
			ans[i] = nl + i - l
(n, m) = map(int, stdin.readline().split())
ans = [0 for i in range(n)]
solve(0, n, 1, n + 1, m - 1)
stdout.write(' '.join(map(str, ans)))


import random, math
from copy import deepcopy as dc
calls = 1

def solution(n, k):
	if k % 2 == 0 or k > 2 * n - 1:
		return -1
	li = [i for i in range(1, n + 1)]

	def mergeCount(li, s, e, k):
		nonlocal calls
		if calls >= k or s >= e - 1:
			return
		mid = (s + e) // 2
		calls += 2
		if mid - 1 >= s:
			(li[mid], li[mid - 1]) = (li[mid - 1], li[mid])
			mergeCount(li, s, mid, k)
			mergeCount(li, mid, e, k)
	mergeCount(li, 0, n, k)
	return li

def input_test():
	(n, k) = list(map(int, input().strip().split(' ')))
	out = solution(n, k)
	if out != -1:
		print(' '.join(list(map(str, out))))
	else:
		print(out)
input_test()


def gbpx(i, j):
	global k
	if k == 1:
		return
	elif j - i == 1:
		return
	else:
		k -= 2
		mid = (i + j) // 2
		a = s[mid - 1]
		b = s[mid]
		s[mid - 1] = b
		s[mid] = a
		gbpx(i, mid)
		gbpx(mid, j)
(n, k) = map(int, input().split())
s = [i for i in range(1, n + 1)]
if k % 2 == 0 or k > n * 2:
	print(-1)
else:
	gbpx(0, n)
	for i in range(0, n):
		print('%d ' % s[i], end='')


def swap(m, n):
	temp = arr[m]
	arr[m] = arr[n]
	arr[n] = temp

def swap_and_modify(arr, l, r, k):
	global count
	if count >= k or r - l < 2:
		return
	else:
		m = int((l + r) / 2)
		swap(m, m - 1)
		count += 2
		swap_and_modify(arr, l, m, k)
		swap_and_modify(arr, m, r, k)
(n, k) = input().split()
n = int(n)
k = int(k)
arr = []
global count
count = 1
for i in range(1, n + 1):
	arr.append(i)
swap_and_modify(arr, 0, n, k)
if count != k:
	print(-1)
else:
	for i in arr:
		print(i, end=' ')


from sys import stdin, setrecursionlimit, stdout
from collections import deque
from math import sqrt, floor, ceil, log, log2, log10, pi, gcd, sin, cos, asin
from heapq import heapify, heappop, heappush, heapreplace, heappushpop
from bisect import bisect_right, bisect_left

def ii():
	return int(stdin.readline())

def fi():
	return float(stdin.readline())

def mi():
	return map(int, stdin.readline().split())

def fmi():
	return map(float, stdin.readline().split())

def li():
	return list(mi())

def si():
	return stdin.readline().rstrip()

def lsi():
	return list(si())
mod = 1000000007
res = ['NO', 'YES']

def merge(l, r):
	global k
	if k:
		m = (l + r) // 2
		if m and l + 1 != r:
			(a[m - 1], a[m]) = (a[m], a[m - 1])
			k -= 2
			merge(l, m)
			merge(m, r)
		return
	return
test = 1
test_case = 1
while test <= test_case:
	test += 1
	(n, k) = mi()
	if not k % 2 or k >= n + n:
		print(-1)
		exit()
	k -= 1
	a = [i + 1 for i in range(n)]
	merge(0, n)
	print(*a)


from sys import setrecursionlimit as c
c(10000)

def s(a, le, ri):
	global k
	if k <= 0 or le >= ri - 1:
		return
	k -= 2
	mid = (le + ri) // 2
	(a[mid], a[mid - 1]) = (a[mid - 1], a[mid])
	s(a, le, mid)
	s(a, mid, ri)
(n, k) = map(int, input().split())
if not k % 2:
	print('-1')
else:
	k -= 1
	l = list(range(1, n + 1))
	s(l, 0, n)
	if not k:
		print(*l)
	else:
		print('-1')


import math
import collections
import bisect
import heapq
import time
import random
(n, k) = map(int, input().split())
if k & 1 == 0 or k > 2 * n - 1:
	print(-1)
else:
	a = [0] * n
	gs = (k - 1) // 2

	def unsort(l, r, v):
		if l == r - 1:
			a[l] = v
		else:
			global gs
			if gs > 0:
				gs -= 1
				mid = (l + r) // 2
				unsort(l, mid, v + r - mid)
				unsort(mid, r, v)
			else:
				for i in range(r - l):
					a[l + i] = v + i
	unsort(0, n, 1)
	print(' '.join([str(x) for x in a]))


(n, k) = list(map(int, input().split()))
lst = [i for i in range(1, n + 1)]

def rearrange(l, r):
	nonlocal k
	if k < 1 or l + 1 == r:
		return
	k -= 2
	mid = (l + r) // 2
	(lst[mid - 1], lst[mid]) = (lst[mid], lst[mid - 1])
	rearrange(l, mid)
	rearrange(mid, r)
if k % 2 == 0 or n * 2 < k:
	print(-1)
else:
	k -= 1
	rearrange(0, n)
	print(' '.join((str(i) for i in lst)))


(n, k) = [int(x) for x in input().split()]
if k % 2 == 0:
	print(-1)
elif k > 2 * n - 1:
	print(-1)
else:
	arr = [n - x for x in range(n)]
	sorts = 2 * n - 1 - k
	segs = [[(0, n, n // 2)]]
	layers = 0
	nCopy = n
	while nCopy:
		layers += 1
		nCopy //= 2
	for x in range(layers):
		newSeg = []
		for (l, r, mid) in segs[x]:
			if mid - l > 1:
				newSeg.append((l, mid, (mid + l) // 2))
			if r - mid > 1:
				newSeg.append((mid, r, (mid + r) // 2))
		segs.append(newSeg)
	for x in range(sorts // 2):
		while not segs[-1]:
			segs.pop()
		(l, r, mid) = segs[-1].pop()
		newPart = arr[mid:r] + arr[l:mid]
		arr[l:r] = newPart
	print(' '.join([str(x) for x in arr]))


from sys import exit
(n, k) = [int(i) for i in input().split()]
if k % 2 == 0 or k >= 2 * n:
	print(-1)
	exit(0)
last = n
a = [0] * n

def ans(c, l, r):
	global last
	if c == 1:
		i = r - 1
		while i >= l:
			a[i] = last
			last -= 1
			i -= 1
		return
	m = (l + r) // 2
	ans(c // 2 - int(c // 2 % 2 == 0), l, m)
	ans(c // 2 + int(c // 2 % 2 == 0), m, r)
ans(k, 0, n)
print(*a)


def fun(arr, l, r, cnt, k, flag):
	if cnt[0] == k:
		flag[0] += 1
		return
	if l == r - 1:
		return
	m = (l + r) // 2
	(arr[m], arr[m - 1]) = (arr[m - 1], arr[m])
	if flag[0] == 0:
		cnt[0] += 2
		fun(arr, l, m, cnt, k, flag)
	if flag[0] == 0:
		fun(arr, m, r, cnt, k, flag)
(n, k) = list(map(int, input().split()))
if k % 2 == 0:
	print(-1)
else:
	arr = [i for i in range(1, n + 1)]
	cnt = [1]
	flag = [0]
	fun(arr, 0, n, cnt, k, flag)
	if cnt[0] != k:
		print(-1)
	else:
		print(' '.join(map(str, arr)))


(n, k) = [int(i) for i in input().split()]
if k % 2 == 0 or k >= 2 * n:
	print(-1)
	return
last = n
a = [0] * n

def ans(c, l, r):
	nonlocal last
	if c == 1:
		i = r - 1
		while i >= l:
			a[i] = last
			last -= 1
			i -= 1
		return
	m = (l + r) // 2
	ans(c // 2 - int(c // 2 % 2 == 0), l, m)
	ans(c // 2 + int(c // 2 % 2 == 0), m, r)
ans(k, 0, n)
print(*a)