問題文
正整数 N,K が与えられます. 1 から N までの整数からなる順列 A=(A1,A2,ldots,AN) であって次の条件を満たすもののうち, 辞書順最小のものを求めてください.
- 任意の i (1leqileqN) に対して lvertAi−irvertgeqK が成り立つ.
そのような順列が存在しない場合には,-1
を出力してください.
数列の辞書順とは?
相異なる数列 S と数列 T の大小を判定するアルゴリズムを以下に説明します.
以下では S の i 番目の要素を Si のように表します.また, S が T より辞書順で小さい場合は SltT ,大きい場合は SgtT と表します.
- S と T のうち長さが短い方の文字列の長さを L とします.i=1,2,dots,L に対して Si と Ti が一致するか調べます.
- SineqTi である i が存在する場合,そのような i のうち最小のものを j とします.そして,Sj と Tj を比較して, Sj が Tj より(数として)小さい場合は SltT ,大きい場合は SgtT と決定して,アルゴリズムを終了します.
- SineqTi である i が存在しない場合, S と T の長さを比較して,S が T より短い場合は SltT ,長い場合は SgtT と決定して,アルゴリズムを終了します.
制約
- 2leqNleq3times105
- 1leqKleqN−1
入力
入力は以下の形式で標準入力から与えられます.
N K
出力
条件を満たす順列 A のうち,辞書順最小のものを次の形式で出力してください.
A1 A2 ldots AN
そのような順列が存在しない場合には,-1
を出力してください.
入力例 1
3 1
出力例 1
2 3 1
条件を満たす順列は,(2,3,1) と (3,1,2) の 2 つです.例えば (2,3,1) は
- lvertA1−1rvert=1geqK
- lvertA2−2rvert=1geqK
- lvertA3−3rvert=2geqK
であるため条件を満たしています.
入力例 2
8 3
出力例 2
4 5 6 7 8 1 2 3
入力例 3
8 6
出力例 3
-1