Stable Permutation

Time limit3sMemory limit256 MB

Summary

Find the k-th lexicographically smallest permutation of length n whose inversion count is exactly half of all pairs, or report NO if none exists.

Level: Hard8 of 10
Topics: Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

A permutation of length $n$ is a sequence $p_1, p_2, \ldots, p_n$ where each $p_i \in \{1, 2, \ldots, n\}$ and $p_i \neq p_j$ whenever $i \neq j$ . For a pair of positions $i < j$ , the pair $(p_i, p_j)$ is an inversion if $p_i > p_j$ . A permutation is stable if reversing it leaves the number of inversions unchanged. Find the $k$ -th stable permutation of length $n$ in lexicographic order.

Input

The only line contains two integers $n$ and $k$ ( $1 \le n \le 250000$ , $1 \le k \le 10^{18}$ ).

Output

If such a permutation exists, print YES on the first line and the $n$ numbers $p_1, \ldots, p_n$ on the second line. Otherwise, print NO.

Hint

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

Examples2

Example 1
Input
```
4 3
```
Expected output
```
YES
2 4 1 3
```
Example 2
Input
```
4 57
```
Expected output
```
NO
```