18993번 - Permutation 다국어

A permutation of length $n$ is a sequence $p_1, p_2, ... p_n$, where $p_i \in \{1, 2, ..., n\}$ and $\forall _{i \neq j} p_i \neq p_j$. We say that a pair $(p_i, p_j)$, where $i < j$, is an inversion, if $p_i > p_j$. We call a permutation stable, if the number of its inversions does not change after reversing the sequence comprising the permutation.

You are asked to find the $k$-th stable permutation of length $n$ with respect to the lexicographic order.

The only line of the input contains two integers $n, k$ ($1 \le n \le 250\,000$, $1 \le k \le 10^{18}$), denoting the length and the index (in the lexicographic order) of the sought stable permutation, respectively.

If there exists such a permutation, in the first line you should output YES and in the second row, $n$ numbers $p_1,\ldots,p_n$ representing the sought permutation. Otherwise output NO.

There are 6 stable permutations of length $4$: $$ (1, 4, 3, 2),\ (2, 3, 4, 1),\ (2, 4, 1, 3),\  (3, 1, 4, 2),\ (3, 2, 1, 4),\ (4, 1, 2, 3). $$