COCI '14 Contest 6 #4 Kratki

Points: 10 (partial)

Time limit: 0.6s

Memory limit: 32M

Problem type

All of you are probably very familiar with the problem of finding the longest monotone subsequence. You probably think you know all about it. In order to convince us, solve the problem "opposite" to finding the longest monotone subsequence.

For given $N$ ~N~ and $K$ ~K~, find the sequence that consists of numbers from $1$ ~1~ to $N$ ~N~ such that each of the numbers in it appears exactly once and the length of its longest monotone subsequence (ascending or descending) is exactly $K$ ~K~.

Input

The first line of input contains the integers $N$ ~N~ and $K$ ~K~ $(1 \le K \le N \le 10^6)$ ~(1 \le K \le N \le 10^6)~, the length of the sequence and the required length of the longest monotone subsequence.

Output

If the required sequence doesn't exist, output -1 in the first and only line.

If the required sequence exists, output the required sequence of $N$ ~N~ numbers in the first and only line. Separate the numbers with a single space.

The required sequence (if it exists) is not necessarily unique, so you can output any valid sequence.

Sample Input 1

4 3

Sample Output 1

1 4 2 3

Explanation for Sample Output 1

A sequence of length $4$ ~4~ with longest monotone subsequence of length $3$ ~3~ is $(1, 4, 2, 3)$ ~(1, 4, 2, 3)~. The longest monotone sequence is $(1, 2, 3)$ ~(1, 2, 3)~.

Sample Input 2

5 1

Sample Output 2

-1

Sample Input 3

5 5

Sample Output 3

1 2 3 4 5

Comments

0

Stonks commented on Jan. 9, 2026, 2:49 a.m.

This problem has ~~very~~ weak data

I was able to AC with the following incorrect sequence: N, N-1 ... N-K+1, 1, 2 ... K

This is solution obviously wrong, because I had read the question incorrectly (thought a monotone sequence had to be increasing only lol)

Based on the AC of my submission, the test cases probably all have $k > n/2$ ~k > n/2~. Otherwise, it would be impossible for me to AC due to the decreasing section.

Example of an incorrect sol that passes: https://dmoj.ca/submission/7530658

Thanks to TheRZ123 for the help