時間制限:12000ミリ秒
メモリ制限:65536KB
各テストケースに対する時間制限:5000ミリ秒
問題
長さがn(n <= 106)の数列が与えられる。その数列上に、最も左の位置から最も右の位置へ移動する長さがkのスライド窓がある。あなたは、数列上でスライド窓の中にあるk個の数しか見ることができない。各時、スライド窓は、1つ右の位置に動く。たとえば、配列 [1 3 -1 -3 5 3 6 7] があり、k=3であるとする。すると、スライド窓は次のようになる。
| スライド窓の位置 | 最小値 | 最大値 |
| [1 3 -1] -3 5 3 6 7 | -1 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 3 | 7 |
入力
入力は、2行から成る。1行目には、2つの整数n,kが空白区切りで書かれている。2行目には、数列の要素を表すn個の数が空白区切りで書かれている。
出力
出力の1行目には、それぞれの位置でのスライド窓の中の数値の最小値を、空白区切りで出力せよ。また2行目には、最大値を出力せよ。
入力の例
8 3 1 3 -1 -3 5 3 6 7
出力の例
-1 -3 -3 -3 3 3 3 3 5 5 6 7
出典
POJ Monthly--2006.04.28, Ikki