Ordered Permutations
Contest: Codeforces Round 992 (Div. 2)
Difficulty rating: 1600
Tags: bitmasks, combinatorics, constructive algorithms, greedy, math, two pointers

Consider a permutation$$$^{\text{∗}}$$$ $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$. We can introduce the following sum for it$$$^{\text{†}}$$$:

$$$$$$S(p) = \sum_{1 \le l \le r \le n} \min(p_l, p_{l + 1}, \ldots, p_r)$$$$$$

Let us consider all permutations of length $$$n$$$ with the maximum possible value of $$$S(p)$$$. Output the $$$k$$$-th of them in lexicographical$$$^{\text{‡}}$$$order, or report that there are less than $$$k$$$ of them.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^{12}$$$) — the length of the permutation and the index number of the desired permutation.

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

Output format:
For each test case, if there are less than $$$k$$$ suitable permutations, print $$$-1$$$.

Otherwise, print the $$$k$$$-th suitable permutation.

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

Note:
Let us calculate the required sum for all permutations of length $$$3$$$ (ordered lexicographically):

PermutationValue of $$$S(p)$$$$$$[1, 2, 3]$$$$$$10$$$$$$[1, 3, 2]$$$$$$10$$$$$$[2, 1, 3]$$$$$$9$$$$$$[2, 3, 1]$$$$$$10$$$$$$[3, 1, 2]$$$$$$9$$$$$$[3, 2, 1]$$$$$$10$$$

In the first test case, you have to print the second suitable permutation of length $$$3$$$. Looking at the table, we see that it is the permutation $$$[1, 3, 2]$$$.

In the second test case, you have to print the third suitable permutation of length $$$3$$$. Looking at the table, we see that it is the permutation $$$[2, 3, 1]$$$.

Example input:
6
3 2
3 3
4 11
4 6
6 39
7 34

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

Editorial:
These permutations are generated as follows. We will greedily go through the numbers in order from $$$1$$$ to $$$n$$$, and we will put each one either in the first free cell or in the last one. For example, if we want to put $$$4$$$ in the permutation $$$1, 3, \circ, \circ, \dots, \circ, 2$$$, we can put it either in the third cell or in the second from the end. That is, the permutation first increases and then decreases.
We can prove that the greedy algorithm works like this. Let us now want to put the number $$$i$$$. When we put this number, we can immediately say that the minimum on the segments, one of the ends of which is the chosen position, is equal to $$$i$$$ (we do not take into account already placed numbers smaller than $$$i$$$). The number of these segments is equal to $$$n - i + 1$$$. The answer we get is equal to the sum of this fixed number and what we get in the future. Assume we put the number $$$i$$$ not at the end of the array. Let's consider the optimal further answer: $$$[\dots, x_j, \dots] i [\dots, x_j, \dots]$$$. Now let's put $$$i$$$ at the end of the array and leave the order of the following elements unchanged. All segments whose ends lie on elements that are larger than $$$i$$$ may no longer cover the number $$$i$$$, but the sets of numbers larger than $$$i$$$ that they cover have not changed. So the answer got better.
Since we choose one of the ends independently, there are $$$2^{n - 1}$$$ of such permutations, and we can find the $$$k$$$-th one using a simple loop, similar to converting a number into binary notation.