Description

There is a $1 \times n$ array containing $n$ integers.

You are given a plank that can cover $k$ consecutive numbers.

At the beginning, the plank covers the $1 \sim k$ numbers of the array. Each time, move the plank one unit to the right until its right end coincides with the $n$-th number.

Before each move, output the maximum among the numbers currently covered by the plank.

Input Format

The first line contains two integers $n, k$, meaning there are $n$ numbers and the plank can cover $k$ consecutive numbers.

The second line contains $n$ integers, which are the elements of the array.

Output Format

Output $n - k + 1$ lines, one integer per line.

The $i$-th line is the maximum value among the $i \sim i + k - 1$ numbers.

5 3
1 5 3 4 2

5
5
4

Hint

• For $20\%$ of the testdata, $1 \leq k \leq n \leq 10^3$.
• For $50\%$ of the testdata, $1 \leq k \leq n \leq 10^4$.
• For $100\%$ of the testdata, $1 \leq k \leq n \leq 2 \times 10^6$, and each element in the array is a positive integer not exceeding $10^4$.

Translated by ChatGPT 5