CF2040C Ordered Permutations

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.

$ ^{\\text{∗}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ \[2,3,1,5,4\] $ is a permutation, but $ \[1,2,2\] $ is not a permutation ( $ 2 $ appears twice in the array), and $ \[1,3,4\] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

$ ^{\\text{†}} $ For example:

• For the permutation $ \[1, 2, 3\] $ the value of $ S(p) $ is equal to $ \\min(1) + \\min(1, 2) + \\min(1, 2, 3) + \\min(2) + \\min(2, 3) + \\min(3) = $ $ 1 + 1 + 1 + 2 + 2 + 3 = 10 $
• For the permutation $ \[2, 4, 1, 3\] $ the value of $ S(p) $ is equal to $ \\min(2) + \\min(2, 4) + \\min(2, 4, 1) + \\min(2, 4, 1, 3) \\ + $ $ \\min(4) + \\min(4, 1) + \\min(4, 1, 3) \\ + $ $ \\min(1) + \\min(1, 3) \\ + $ $ \\min(3) = $ $ 2 + 2 + 1 + 1 + 4 + 1 + 1 + 1 + 1 + 3 = 17 $ .

$ ^{\\text{‡}} $ An array $ a $ is lexicographically smaller than an array $ b $ if and only if one of the following holds:

• $ a $ is a prefix of $ b $ , but $ a \\ne b $ ; or
• in the first position where $ a $ and $ b $ differ, the array $ a $ has a smaller element than the corresponding element in $ b$$$.

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 $ .

For each test case, if there are less than $ k $ suitable permutations, print $ -1 $ . Otherwise, print the $ k $ -th suitable permutation.

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] $ .