For a given array $a_1, a_2, a_3, ... , a_N$ of $N$ elements and an integer $L$, find the minimum of each possible sub-arrays with size $L$ and print them from the beginning. For example, for an array $\\{1, 7, 7, 4, 8, 1, 6\\}$ and $L = 3$, the possible sub-arrays with size $L = 3$ includes $\\{1, 7, 7\\}$, $\\{7, 7, 4\\}$, $\\{7, 4, 8\\}$, $\\{4, 8, 1\\}$, $\\{8, 1, 6\\}$ and the minimum of each sub-array is 1, 4, 4, 1, 1 respectively.

Constraints

* $1 \leq N \leq 10^6$
* $1 \leq L \leq 10^6$
* $1 \leq a_i \leq 10^9$
* $L \leq N$

Input

The input is given in the following format.

$N$ $L$
$a_1$ $a_2$ ... $a_N$

Output

Print a sequence of the minimum in a line. Print a space character between adjacent elements.

Example

Input

7 3
1 7 7 4 8 1 6


Output

1 4 4 1 1

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from collections import deque
(N, L) = map(int, input().split())
a = list(map(lambda x: int(x), input().split()))
que: deque = deque()
ans = []
for (i, elem) in enumerate(a):
	while que and elem <= que[-1][1]:
		que.pop()
	que.append((i, elem))
	ans.append(que[0][1])
	if que and que[0][0] <= i + 1 - L:
		que.popleft()
print(' '.join([str(elem) for elem in ans[L - 1:]]))


from itertools import accumulate
from collections import deque

class SWAG:

	def __init__(self, operator_M, e_M):
		self.op_M = operator_M
		self.e_M = e_M
		self.q = deque([])
		self.accL = []
		self.accR = e_M
		self.L = self.R = 0

	def build(self, lst):
		self.q = deque(lst)
		self.L = len(lst)
		self.accL = list(accumulate(reversed(self.q), self.op_M))

	def __len__(self):
		return self.L + self.R

	def fold_all(self):
		if self.L:
			return self.op_M(self.accL[-1], self.accR)
		else:
			return self.accR

	def append(self, x):
		self.q.append(x)
		self.accR = self.op_M(self.accR, x)
		self.R += 1

	def popleft(self):
		if self.L:
			self.accL.pop()
			self.L -= 1
			return self.q.popleft()
		elif self.R:
			(self.L, self.R) = (self.R - 1, 0)
			self.accL = list(accumulate(reversed(self.q), self.op_M))
			self.accR = self.e_M
			self.accL.pop()
			return self.q.popleft()
		else:
			assert 0
import sys
readline = sys.stdin.readline
read = sys.stdin.read
(n, l, *a) = [int(i) for i in read().split()]
q = SWAG(min, 10 ** 9)
q.build(a[:l])
ans = [q.fold_all()]
for i in a[l:]:
	q.popleft()
	q.append(i)
	ans.append(q.fold_all())
print(*ans)


from collections import deque
(N, L) = map(int, input().split())
(*A,) = map(int, input().split())
ans = []
que = deque()
for (i, a) in enumerate(A):
	while que and a <= que[-1][1]:
		que.pop()
	que.append((i, a))
	ans.append(que[0][1])
	if que and que[0][0] <= i + 1 - L:
		que.popleft()
print(*ans[L - 1:])


from collections import deque
ans = []
(n, L) = map(int, input().split())
A = list(map(int, input().split()))
que = deque()
for (i, a) in enumerate(A):
	while que and a <= que[-1][1]:
		que.pop()
	que.append((i, a))
	ans.append(que[0][1])
	if que and que[0][0] <= i + 1 - L:
		que.popleft()
ans = ans[L - 1:]
print(*ans)


import collections, numbers
import random

def compute(array, window, maximize):
	if not isinstance(window, numbers.Integral):
		raise TypeError()
	if not isinstance(maximize, bool):
		raise TypeError()
	if window <= 0:
		raise ValueError('Window size must be positive')
	result = []
	deque = collections.deque()
	for (i, val) in enumerate(array):
		val = array[i]
		while len(deque) > 0 and (not maximize and val < deque[-1] or (maximize and val > deque[-1])):
			deque.pop()
		deque.append(val)
		j = i + 1 - window
		if j >= 0:
			result.append(deque[0])
			if array[j] == deque[0]:
				deque.popleft()
	return result

class SlidingWindowMinMax(object):

	def __init__(self):
		self.mindeque = collections.deque()
		self.maxdeque = collections.deque()

	def get_minimum(self):
		return self.mindeque[0]

	def get_maximum(self):
		return self.maxdeque[0]

	def add_tail(self, val):
		while len(self.mindeque) > 0 and val < self.mindeque[-1]:
			self.mindeque.pop()
		self.mindeque.append(val)
		while len(self.maxdeque) > 0 and val > self.maxdeque[-1]:
			self.maxdeque.pop()
		self.maxdeque.append(val)

	def remove_head(self, val):
		if val < self.mindeque[0]:
			raise ValueError('Wrong value')
		elif val == self.mindeque[0]:
			self.mindeque.popleft()
		if val > self.maxdeque[0]:
			raise ValueError('Wrong value')
		elif val == self.maxdeque[0]:
			self.maxdeque.popleft()
(n, l) = (int(x) for x in input().split())
array = list((int(x) for x in input().split()))
answer = compute(array, l, False)
print(*answer)


from collections import deque
(N, L) = map(int, input().split())
(*list,) = map(int, input().split())
ans = []
que = deque()
for (i, num) in enumerate(list):
	while que and num <= que[-1][1]:
		que.pop()
	que.append((i, num))
	ans.append(que[0][1])
	if que and que[0][0] <= i + 1 - L:
		que.popleft()
print(*ans[L - 1:])


(N, L) = list(map(int, input().split()))
alist = list(map(int, input().split()))
arr = []
for i in range(L):
	while arr and alist[i] <= alist[arr[-1]]:
		arr.pop()
	arr.append(i)
for i in range(L, N):
	print(alist[arr[0]], end=' ')
	while arr and arr[0] <= i - L:
		arr.pop(0)
	while arr and alist[i] <= alist[arr[-1]]:
		arr.pop()
	arr.append(i)
print(alist[arr[0]])


def ascend(a, b):
	mini = min(A[a:a + L])
	ans[a] = mini
	for i in range(a + 1, b):
		if A[i + L - 1] <= mini:
			mini = A[i + L - 1]
		elif A[i - 1] == mini:
			mini = min(A[i:i + L])
		ans[i] = mini

def descend(a, b):
	mini = min(A[b - 1:b + L - 1])
	ans[b - 1] = mini
	for i in range(b - 2, a - 1, -1):
		if A[i] <= mini:
			mini = A[i]
		elif A[i + L] == mini:
			mini = min(A[i:i + L])
		ans[i] = mini
[N, L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None] * (N - L + 1)
Pcount = 0
Mcount = 0
if N > 10 ** 4:
	for i in range(100):
		if A[i + 1] > A[i]:
			Pcount += 1
		if A[i + 1] < A[i]:
			Mcount += 1
	if Pcount > 80:
		descend(0, N - L + 1)
	else:
		ascend(0, N - L + 1)
else:
	ascend(0, N - L + 1)
for i in ans[:-1]:
	print(i, end=' ')
print(ans[-1])


from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

class SlidingWindowAggretgation:

	def __init__(self, default=float('inf'), f=min):
		self.default = default
		self.f = f
		self.front_stack = deque()
		self.back_stack = deque()

	def get(self):
		res = self.default
		if self.front_stack:
			res = self.f(res, self.front_stack[-1][1])
		if self.back_stack:
			res = self.f(res, self.back_stack[-1][1])
		return res

	def append(self, x):
		fx = x
		if self.back_stack:
			fx = self.f(self.back_stack[-1][1], x)
		self.back_stack.append((x, fx))

	def popleft(self):
		if not self.front_stack:
			(x, fx) = self.back_stack.pop()
			self.front_stack.append((x, x))
			while self.back_stack:
				(x, fx) = self.back_stack.pop()
				fx = self.f(x, self.front_stack[-1][1])
				self.front_stack.append((x, fx))
		self.front_stack.pop()

def solve():
	(n, l) = LI()
	a = LI()
	swag = SlidingWindowAggretgation()
	ans = []
	for i in range(n):
		swag.append(a[i])
		if i + 1 >= l:
			ans.append(swag.get())
			swag.popleft()
	print(*ans)
	return
solve()


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

class SWAG(object):

	def __init__(self, dot):
		self.__front = []
		self.__back = []
		self.__dot = dot

	def __bool__(self):
		return True if self.__front or self.__back else False

	def __len__(self):
		return len(self.__front) + len(self.__back)

	def sum(self):
		assert self
		front = self.__front
		back = self.__back
		if not front:
			return back[-1][1]
		elif not back:
			return front[-1][1]
		else:
			return self.__dot(front[-1][1], back[-1][1])

	def append(self, x):
		back = self.__back
		if not back:
			back.append((x, x))
		else:
			back.append((x, self.__dot(back[-1][1], x)))

	def popleft(self):
		assert self
		front = self.__front
		back = self.__back
		if not front:
			front.append((back[-1][0], back[-1][0]))
			back.pop()
			while back:
				front.append((back[-1][0], self.__dot(back[-1][0], front[-1][1])))
				back.pop()
		front.pop()

def resolve():
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	ans = [None] * n
	swag = SWAG(min)
	for (i, a) in enumerate(A):
		swag.append(a)
		ans[i] = swag.sum()
		if i - k + 1 >= 0:
			swag.popleft()
	print(*ans[k - 1:])
resolve()


from collections import deque
(N, L) = map(int, input().split())
box = list(map(int, input().split()))
que = deque()
ans = []
for (i, a) in enumerate(box):
	while que and a <= que[-1][1]:
		que.pop()
	que.append((i, a))
	ans.append(que[0][1])
	if que and que[0][0] <= i - L + 1:
		que.popleft()
print(*ans[L - 1:])


def ascend(a, b):
	mini = min(A[a:a + L])
	ans[a] = mini
	for i in range(a + 1, b):
		if A[i + L - 1] <= mini:
			mini = A[i + L - 1]
		elif A[i - 1] == mini:
			mini = min(A[i:i + L])
		ans[i] = mini

def descend(a, b):
	mini = min(A[b - 1:b + L - 1])
	ans[b - 1] = mini
	for i in range(b - 2, a - 1, -1):
		if A[i] <= mini:
			mini = A[i]
		elif A[i + L] == mini:
			mini = min(A[i:i + L])
		ans[i] = mini
[N, L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None] * (N - L + 1)
count = 0
if N > 10 ** 4:
	for i in range(100):
		if A[i + 1] > A[i]:
			count += 1
	if count > 80:
		descend(0, N - L + 1)
	else:
		ascend(0, N - L + 1)
else:
	ascend(0, N - L + 1)
for i in ans[:-1]:
	print(i, end=' ')
print(ans[-1])


import collections, numbers
import random

def compute(array, window, maximize):
	if not isinstance(window, numbers.Integral):
		raise TypeError()
	if not isinstance(maximize, bool):
		raise TypeError()
	if window <= 0:
		raise ValueError('Window size must be positive')
	result = []
	deque = collections.deque()
	for (i, val) in enumerate(array):
		val = array[i]
		while len(deque) > 0 and (not maximize and val < deque[-1] or (maximize and val > deque[-1])):
			deque.pop()
		deque.append(val)
		j = i + 1 - window
		if j >= 0:
			result.append(deque[0])
			if array[j] == deque[0]:
				deque.popleft()
	return result
(n, l) = (int(x) for x in input().split())
array = list((int(x) for x in input().split()))
answer = compute(array, l, False)
print(*answer)


import sys

def get_sliding_minimum_element(nums, k):
	res = []
	queue = []
	for (i, v) in enumerate(nums):
		if queue and queue[0] <= i - k:
			queue = queue[1:]
		while queue and nums[queue[-1]] > v:
			queue.pop()
		queue.append(i)
		if i + 1 >= k:
			res.append(nums[queue[0]])
	return res
b = [0 for _ in range(1000000)]
deq = [0 for _ in range(1000000)]
line = sys.stdin.readline()
(n, l) = map(int, line.split())
arr = list(map(int, input().split()))
s = 0
t = 0
for i in range(n):
	while s < t and arr[deq[t - 1]] >= arr[i]:
		t -= 1
	deq[t] = i
	t += 1
	if i - l + 1 >= 0:
		b[i - l + 1] = arr[deq[s]]
		if deq[s] == i - l + 1:
			s += 1
for i in range(n - l + 1):
	if i == n - l:
		print(str(b[i]), end='')
	else:
		print(str(b[i]) + ' ', end='')
print('\n', end='')


from heapq import heappush, heappop

def run():
	(_, size) = [int(x) for x in input().split()]
	heap = []
	removed = set()
	result = []
	n = 0
	for (i, v) in enumerate(input().split()):
		heappush(heap, (int(v), i))
		n += 1
		if n > size:
			removed.add(i - size)
			n -= 1
		if n == size:
			while len(heap) > 0:
				(minv, k) = heap[0]
				if k in removed:
					removed.remove(k)
					heappop(heap)
				else:
					result.append(str(minv))
					break
	print(' '.join(result))
run()


from collections import deque

def slide_min(L: int, li: list):
	deq = deque()
	ret = []
	for (i, x) in enumerate(li):
		while deq and deq[-1][1] > x:
			deq.pop()
		deq.append((i, x))
		if deq[0][0] + L == i:
			deq.popleft()
		ret.append(deq[0][1])
	return ret[L - 1:]

def main():
	(n, l, *a) = map(int, open(0).read().split())
	print(*slide_min(l, a))
main()


import sys, math, itertools, collections, bisect
input = lambda : sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
mod = 10 ** 9 + 7
mans = inf
ans = 0
count = 0
pro = 1

class SWAG:

	def __init__(self, func, ide):
		self.ide = ide
		self.func = func
		self.front = []
		self.back = []

	def push(self, x):
		if self.back:
			y = self.func(self.back[-1][1], x)
		else:
			y = x
		self.back.append((x, y))

	def pop(self):
		if not self.front:
			while self.back:
				(x, y) = self.back.pop()
				if self.front:
					y = self.func(self.front[-1][1], x)
				else:
					y = x
				self.front.append((x, y))
		return self.front.pop()[1]

	def fold_all(self):
		y = self.ide
		if self.front:
			y = self.func(self.front[-1][1], y)
		if self.back:
			y = self.func(self.back[-1][1], y)
		return y
ans = []
(n, l) = map(int, input().split())
data = list(map(int, input().split()))
swag = SWAG(min, inf)
for i in range(l - 1):
	swag.push(data[i])
for i in range(l - 1, n):
	swag.push(data[i])
	ans.append(swag.fold_all())
	swag.pop()
print(*ans)


import collections
(N, L) = map(int, input().split())
a = list(map(int, input().split()))
deq = collections.deque()
ans = []
for i in range(N):
	while deq and a[i] <= deq[-1][1]:
		deq.pop()
	deq.append((i, a[i]))
	ans.append(deq[0][1])
	if deq and deq[0][0] <= i - L + 1:
		deq.popleft()
print(*ans[L - 1:N])


def ascend(x, y):
	mini = min(A[x:x + L])
	ans[x] = mini
	for i in range(x + 1, y):
		if A[i + L - 1] <= mini:
			mini = A[i + L - 1]
		elif A[i - 1] == mini:
			mini = min(A[i:i + L])
		ans[i] = mini

def descend(a, b):
	mini = min(A[b - 1:b + L - 1])
	ans[b - 1] = mini
	for i in range(b - 2, a - 1, -1):
		if A[i] <= mini:
			mini = A[i]
		elif A[i + L] == mini:
			mini = min(A[i:i + L])
		ans[i] = mini
[N, L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None] * (N - L + 1)
count = 0
if N > 10 ** 4:
	for i in range(100):
		if A[i + 1] > A[i]:
			count += 1
	if count > 80:
		descend(0, N - L + 1)
	else:
		ascend(0, N - L + 1)
else:
	ascend(0, N - L + 1)
for i in ans[:-1]:
	print(i, end=' ')
print(ans[-1])


INTMAX = (1 << 31) - 1

def ans():
	for i in range(k):
		x = i + OFS
		A[x] = arr[i]
		while True:
			if x <= 0:
				break
			x = (x - 1) // 2
			l = A[x * 2 + 1]
			r = A[x * 2 + 2]
			A[x] = l if l < r else r
	res = []
	c = 0
	for i in range(_N - k):
		res.append(A[0])
		x = c + OFS
		A[x] = arr[i + k]
		while True:
			if x <= 0:
				break
			x = (x - 1) // 2
			l = A[x * 2 + 1]
			r = A[x * 2 + 2]
			A[x] = l if l < r else r
		c += 1
		if c == k:
			c = 0
	res.append(A[0])
	print(*res)
(_N, k) = map(int, input().split())
(*arr,) = map(int, input().split())
if k == 1:
	print(*arr)
else:
	N = 2 ** (_N - 1).bit_length()
	A = [INTMAX] * (2 * N)
	OFS = N - 1
	ans()


import collections

def sme():
	for (cur, M) in enumerate(element):
		while que and M <= que[-1][1]:
			que.pop()
		que.append((cur, M))
		res.append(que[0][1])
		if que and que[0][0] == cur - L + 1:
			que.popleft()
(N, L) = map(int, input().split())
element = list(map(int, input().split()))
que = collections.deque()
res = []
sme()
print(*res[L - 1:])


from collections import deque
(N, L) = map(int, input().split())
A = list(map(int, input().split()))
ans = []
q = deque()
for (i, a) in enumerate(A):
	while q and A[q[-1]] >= a:
		q.pop()
	q.append(i)
	if i - L + 1 >= 0:
		ans.append(A[q[0]])
		if q[0] == i - L + 1:
			q.popleft()
print(*ans)