1323 - Non-subsequential Sequence
問題
長さ $N$ の数列 $A = \{a_1, a_2, \ldots ,a_N \}$ と正整数 $M$ が与えられます。
以下の条件を満たす数列を出力してください。
- $1$ 以上 $M$ 以下の整数からなる。
- $A$ の部分列でない。
- 1, 2 を満たすものの中で数列長が最小である。
- 3 を満たすものの中で総和が最大である。
ここで、$A$ の部分列とは $A$ から要素を $0$ 個以上 $N$ 個未満取り除き、残った要素を元の順番で並べることによって得られる数列とします。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$ $a_1$ $a_2$ $\ldots$ $a_N$
出力
条件を満たす数列の各要素を空白区切りで出力せよ。
条件を満たす数列が複数考えられる場合は、いずれを出力しても良いものとする。
ただし、以下のことに注意すること。
- 出力の末尾には改行を入れる。
- 余分な空白を出力してはならない。
制約
- $1 \leq N \leq 1000$
- $1 \leq M \leq 1000$
- $1 \leq a_i \leq 1000 \ (1 \leq i \leq N)$
- 入力はすべて整数である。
入出力例
入力例１
4 3 1 1 2 3
出力例１
3 3
条件3を満たす数列として考えられるものは、$\{ 2, 2 \}$ と $\{ 3, 3 \}$ です。
このうち条件4を満たす数列は $\{ 3, 3 \}$ です。
入力例２
2 3 1 2
出力例２
3
入力例３
5 1 1 1 1 1 1
出力例３
1 1 1 1 1 1
入力例４
38 6 10 9 6 3 6 2 7 5 7 1 10 4 4 6 1 3 10 3 8 1 2 8 1 1 1 7 8 3 8 10 9 9 9 1 8 1 5 5
出力例４
5 6 6