package main
import(
“fmt”
“os”
“bufio”
)
const N int = 1000010
var a [N]int
var b [N]int
var h , t int
var n , k int
var reader = bufio.NewReader(os.Stdin)
func init(){
h = 1
}
func popBack(){
t –
}
func popFront(){
h ++
}
func push(x int){
t ++
b[t] = x
}
func clear(){
h = 1
t = 0
b = [N]int{}
}
func main(){
fmt.Fscan(reader,&n,&k)
for i:=0;i<n;i++{
fmt.Fscan(reader,&a[i])
}
for i:=0;i<n;i++{
for h <= t && b[t] > a[i]{
popBack()
}
push(a[i])
if i - k + 1 >= 1 && b[h] == a[i-k]{
popFront()
}
if i + 1 >= k{
fmt.Printf("%d ",b[h])
}
}
fmt.Println()
clear()
for i:=0;i<n;i++{
for h <= t && b[t] < a[i]{
popBack()
}
push(a[i])
if i - k + 1 >= 1 && b[h] == a[i-k]{
popFront()
}
if i + 1 >= k{
fmt.Printf("%d ",b[h])
}
}
}