Exact Longest Monotone Subsequence

Time limit1sMemory limit256 MB

Summary

Build the lexicographically smallest permutation of 1 to N whose longest increasing or decreasing subsequence has length exactly K, or print -1 when impossible.

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

Problem

Finding the longest monotone subsequence of a given sequence is a well known exercise. This task turns it around: you build the sequence yourself.

For given $N$ and $K$ , find a sequence in which every number from $1$ to $N$ appears exactly once and whose longest monotone subsequence has length exactly $K$ . A monotone subsequence is one that is increasing or decreasing.

A subsequence keeps the order of the original sequence, and the chosen elements do not have to be adjacent. An increasing subsequence has values that keep growing, a decreasing subsequence has values that keep shrinking.

Input

The first line contains the length of the sequence $N$ and the required length of the longest monotone subsequence $K$ , separated by a single space. ( $1 \le K \le N \le 10^6$ )

Output

If no such sequence exists, print $-1$ on the first line.

If such a sequence exists, print on the first line the lexicographically smallest one among the sequences that satisfy the condition. Write the $N$ numbers on one line, separated by single spaces.

To compare two sequences lexicographically, find the first position where they differ, and treat the sequence with the smaller number at that position as the earlier one.

Hint

For $N = 4$ and $K = 3$ the sequence $(1, 4, 2, 3)$ also satisfies the condition. Its longest monotone subsequence is $(1, 2, 3)$ , of length $3$ . The lexicographically smallest sequence that satisfies the condition is $(1, 2, 4, 3)$ , so that one is the answer.

Examples3

Example 1
Input
```
4 3
```
Expected output
```
1 2 4 3
```
Example 2
Input
```
5 1
```
Expected output
```
-1
```
Example 3
Input
```
5 5
```
Expected output
```
1 2 3 4 5
```