Sim-4-15 | Balama

At the woodworking exam, the future engineers were given a door with $N$ hinges, each with a resistance $R_1, \dots, R_N$.

The first test of the exam consists of determining the total resistance of the door, which is a sequence $T_1, \dots, T_K$ formed of $K$ numbers, computed as follows.

First, we define the matrix $A_{ij}$ with $N - K + 1$ rows and $K$ columns, such that the $i$-th row of $A$ is the subsequence $R_i, \dots, R_{i+K-1}$ of the sequence $R$. For example, if $N = 9$, $R = [2, 5, 4, 3, 2, 1, 8, 7, 3]$ and $K = 3$, then:

Then, we define the matrix $B_{ij}$, also with $N - K + 1$ rows and $K$ columns, such that the $i$-th row of $B$ contains exactly the elements of row $i$ of matrix $A$, but sorted in increasing order. For example, for the previous values of $N$ and $R$ we have that:

Finally, we define $T_j$ as the maximum of column $j$ of $B$, that is, $T_j = \max_i B_{ij}$. In the example above, the column maximums are $3$, $7$, $8$, and are boxed.

Requirement

Given $N$, $K$, and $R_1, \dots, R_N$, compute $T_1, \dots, T_K$.

Input Data

The first line of the file balama.in will contain the numbers $N$ and $K$, with the meaning given in the statement. On the next line will be the resistances of the $N$ hinges $R_1, \dots, R_N$, separated by spaces.

Output Data

The output file balama.out will contain $K$ numbers separated by spaces, the $i$-th number representing $T_i$.

Constraints and Notes

• $1 \leq N \leq 200 \ 000$
• $1 \leq K \leq N$
• $0 \leq R_i \leq 10^9$ for $1 \leq i \leq N$

Note: Subtask 5 contains five groups of tests, worth $7$, $8$, $8$, $9$, and $10$ points respectively.

Example

balama.in

9 3
2 5 4 3 2 1 8 7 3

balama.out

3 7 8

Explanation

Matrix $A$ has the values
$\begin{pmatrix} 2 & 5 & 4\\ 5 & 4 & 3\\ 4 & 3 & 2\\ 3 & 2 & 1\\ 2 & 1 & 8\\ 1 & 8 & 7\\ 8 & 7 & 3 \end{pmatrix}$

Matrix $B$ has the values
$\begin{pmatrix} 2 & 4 & 5\\ 3 & 4 & 5\\ 2 & 3 & 4\\ 1 & 2 & 3\\ 1 & 2 & 8\\ 1 & 7 & 8\\ 3 & 7 & 8 \end{pmatrix}$

The column maximums are $3$, $7$, $8$.