Сортировка слиянием — один из самых известных алгоритмов сортировки. Основная функция этого алгоритма, сортирующая промежуток массива a с индексами из [l, r), может быть реализована следующим образом:

1. Если промежуток [l, r) уже отсортирован в неубывающем порядке (то есть, для каждого i, такого, что l ≤ i < r - 1, a[i] ≤ a[i + 1]), завершить вызов функции;
2. Присвоить ;
3. Вызвать mergesort(a, l, mid);
4. Вызвать mergesort(a, mid, r);
5. Слить промежутки [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.

Помогите Ивану найти нужный массив!