AT_past202004_l 辞書順最小

### 题目简述 给出一个长为 $n$ 的整数序列 $a_1,a_2,...,a_n$。现在要从中选出 $k$ 个元素，并将它们按原来的相对位置排序以形成一个新的序列。选出的任意一对数 $(a_i,a_j)$ 中，满足 $|i-j| \ge d$（$i \neq j$）。请找出可以形成的字典序最小的序列。若无法找出满足条件的序列，输出`-1`。

第一行：$n,k,d$ 第二行：$a_1,a_2,...,a_n$

若有解请输出答案序列；否则输出`-1`。 ### 约束条件 $2 \le n \le 2 \times 10^5$； $1 \le d,k \le n$； $0 \le a_i \le 10^9$； 输入的数值均为整数。

### 注意 この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ D\ \leq\ N $ - $ 1\ \leq\ K\ \leq\ N $ - $ 0\ \leq\ A_i\ \leq\ 10^9 $ - 入力は全て整数 ### Sample Explanation 1 数列 $ A $ は $ \{\ 3,\ 1,\ 4\} $ です。$ D\ =\ 2 $ の下で、$ K\ =\ 2 $ 個の要素を選んで数列を作る方法は次の $ 1 $ 通りです。 - $ A $ の $ 1,\ 3 $ 番目の要素を選び、$ \{\ 3,\ 4\} $ とする。 よって、$ \{\ 3,\ 4\} $ を出力してください。 ### Sample Explanation 2 数列 $ A $ は $ \{\ 3,\ 1,\ 4\} $ です。$ D\ =\ 2 $ の下で、$ K\ =\ 3 $ 個の要素を選んで数列を作ることはできません。 よって、$ -1 $ を出力してください。 ### Sample Explanation 3 数列 $ A $ は $ \{\ 3,\ 1,\ 4\} $ です。$ D\ =\ 1 $ の下で、$ K\ =\ 2 $ 個の要素を選んで数列を作る方法は次の $ 3 $ 通りです。 - $ A $ の $ 1,\ 2 $ 番目の要素を選び、$ \{\ 3,\ 1\} $ とする。 - $ A $ の $ 1,\ 3 $ 番目の要素を選び、$ \{\ 3,\ 4\} $ とする。 - $ A $ の $ 2,\ 3 $ 番目の要素を選び、$ \{\ 1,\ 4\} $ とする。 よって、$ \{\ 1,\ 4\} $ を出力してください。 ### Sample Explanation 4 数列 $ A $ は $ \{\ 3,\ 6,\ 5,\ 5\} $ です。$ D\ =\ 2 $ の下で、$ K\ =\ 2 $ 個の要素を選んで数列を作る方法は次の $ 3 $ 通りです。 - $ A $ の $ 1,\ 3 $ 番目の要素を選び、$ \{\ 3,\ 5\} $ とする。 - $ A $ の $ 1,\ 4 $ 番目の要素を選び、$ \{\ 3,\ 5\} $ とする。 - $ A $ の $ 2,\ 4 $ 番目の要素を選び、$ \{\ 6,\ 5\} $ とする。 よって、$ \{\ 3,\ 5\} $ を出力してください。