Almost Sorted
Contest: Codeforces Round 715 (Div. 1)
Difficulty rating: 1800
Tags: binary search, combinatorics, constructive algorithms, implementation

Seiji Maki doesn't only like to observe relationships being unfolded, he also likes to observe sequences of numbers, especially permutations. Today, he has his eyes on almost sorted permutations.

A permutation $$$a_1, a_2, \dots, a_n$$$ of $$$1, 2, \dots, n$$$ is said to be almost sorted if the condition $$$a_{i + 1} \ge a_i - 1$$$ holds for all $$$i$$$ between $$$1$$$ and $$$n - 1$$$ inclusive.

Maki is considering the list of all almost sorted permutations of $$$1, 2, \dots, n$$$, given in lexicographical order, and he wants to find the $$$k$$$-th permutation in this list. Can you help him to find such permutation?

Permutation $$$p$$$ is lexicographically smaller than a permutation $$$q$$$ if and only if the following holds:

- in the first position where $$$p$$$ and $$$q$$$ differ, the permutation $$$p$$$ has a smaller element than the corresponding element in $$$q$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1\le t\le 1000$$$) — the number of test cases.

Each test case consists of a single line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le k \le 10^{18}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, print a single line containing the $$$k$$$-th almost sorted permutation of length $$$n$$$ in lexicographical order, or $$$-1$$$ if it doesn't exist.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first and second test, the list of almost sorted permutations with $$$n = 1$$$ is $$$\{[1]\}$$$.

For the third and fifth test, the list of almost sorted permutations with $$$n = 3$$$ is $$$\{[1, 2, 3], [1, 3, 2], [2, 1, 3], [3, 2, 1]\}$$$.

Example input:
5
1 1
1 2
3 3
6 5
3 4

Example output:
1 
-1
2 1 3 
1 2 4 3 5 6 
3 2 1

Editorial:
First solution.
Let's first analyze the general structure of an almost sorted permutation. We know that when the sequence decreases, it must decrease by exactly $$$1$$$. Thus, every decreasing subarray covers some consecutive range of values. Let's split the permutation into decreasing subarrays, each of them as large as possible. For example, we can split the almost sorted permutation $$$[3, 2, 1, 4, 6, 5, 7]$$$ as $$$[3, 2, 1], [4], [6, 5], [7]$$$. The main claim goes as follows.
Claim. Each almost sorted permutation is determined uniquely by the sequence of sizes of its maximal decreasing subarrays.
So for instance, in the previous example, the sequence of sizes $$$3, 1, 2, 1$$$ uniquely determines the permutation as $$$[3, 2, 1, 4, 6, 5, 7]$$$. This is because the last element $$$a_i$$$ of a decreasing block must be smaller than the first element $$$a_{i + 1}$$$ in the next block. Otherwise we either have $$$a_{i + 1} = a_i - 1$$$, in which case we should expand the previous block, or $$$a_{i + 1} < a_i - 1$$$, which is contradictory.
Now, this is basically enough to get a complete solution. Through some careful counting (which we will go into detail about later) we can show that there are $$$2^{n - 1}$$$ almost sorted permutations of size $$$n$$$. Now notice that smaller sizes for the first block produce lexicographically smaller permutations (since a permutation whose first block has size $$$m$$$ starts with $$$m$$$). Moreover, the remaining sequence after deleting the first block is almost sorted. This enables to do a recursive argument to find the permutation, by first choosing the correct size for the first block and then solving recursively for the remaining sequence. This works in $$$\mathcal{O}(n \log k)$$$.
Second solution.
But we can do better. Let's mark the positions in the array where a decreasing block ends with $$$0$$$, and the other positions as $$$1$$$. Notice that the last character is always $$$0$$$, so we will ignore it and assign only the other $$$n - 1$$$ characters. Thus our example permutation $$$[3, 2, 1, 4, 6, 5, 7]$$$ becomes $$$110010$$$ since the first, second, and third blocks end at positions $$$3$$$, $$$4$$$, and $$$6$$$. By the first claim, we can recover the permutation from this sequence (which is also the proof of there being $$$2^{n - 1}$$$ permutations of size $$$n$$$ that we promised earlier!).
Now, we can read the assigned sequence as a binary number, for instance, the corresponding number is $$$110010_2 = 2^5 + 2^4 + 2^1 = 50$$$ for our trusty example. The point of doing this is the following:
Claim 2. The $$$k$$$-th almost sorted permutation in lexicographical order is assigned the number $$$k - 1$$$.
To prove this it's actually enough to check that the number $$$m + 1$$$ is assigned to a greater permutation than the number $$$m$$$. This can be done by looking at how the permutation changes when we add $$$1$$$ to $$$m$$$, looking at the binary representation of $$$m$$$ from right to left. We leave it to the reader to fill in the details of the proof, but here's a diagram showing the situation graphically (with height representing the values of the permutation).
Anyways, once we have proven this claim, we get a simple $$$\mathcal{O}(n + \log k)$$$ solution by finding the binary representation of $$$k$$$ and using it to reconstruct the blocks in $$$\mathcal{O}(n)$$$.