Сортировка слиянием — один из самых известных алгоритмов сортировки. Основная функция этого алгоритма, сортирующая промежуток массива a с индексами из [l, r), может быть реализована следующим образом:
- Если промежуток [l, r) уже отсортирован в неубывающем порядке (то есть, для каждого i, такого, что l ≤ i < r - 1, a[i] ≤ a[i + 1]), завершить вызов функции;
- Присвоить
; - Вызвать mergesort(a, l, mid);
- Вызвать mergesort(a, mid, r);
- Слить промежутки [l, mid) и [mid, r) воедино, после чего промежуток [l, r) будет отсортирован в неубывающем порядке. Функция слияния не вызывает никаких других функций.
В этой задаче массив 0-индексирован, и для сортировки всего массива нужно вызвать mergesort(a, 0, n).
Количество вызовов функции mergesort очень важно, поэтому Иван решил вычислять его во время сортировки. К примеру, если a = {1, 2, 3, 4}, то будет сделан 1 вызов mergesort — mergesort(0, 4), который проверит, что массив отсортирован, и завершится. Если a = {2, 1, 3}, то количество вызовов равно 3: сначала вызывается mergesort(0, 3), в котором присваивается mid = 1 и вызывается calls mergesort(0, 1) и mergesort(1, 3), не проводящие никаких рекурсивных вызовов, так как подотрезки (0, 1) и (1, 3) уже отсортированы.
Иван написал программу, которая считает число вызовов функции mergesort, но сейчас ему нужно протестировать её. Для этого необходимо найти массив a, такой, что a — перестановка первых n чисел (то есть размер a равен n, и каждое целое число из [1, n] встречается в массиве ровно один раз), и число вызовов mergesort при сортировке этого массива равно k.
Помогите Ивану найти нужный массив!
Выходные данные
Если перестановка размера n, такая, что при её сортировке будет совершено ровно k вызовов mergesort, не существует, выведите - 1. Иначе выведите n целых чисел a[0], a[1], ..., a[n - 1] — элементы перестановки. Если решений несколько, выведите любое.