Background

Translated from D1T1 of Izborne Pripreme 2019 (Croatian IOI/CEOI Team Selection). $\texttt{2s,0.5G}$.

Problem Description

You are given a sequence of positive integers $a_0, a_1, \cdots, a_{N-1}$ of length $N$ and a positive integer $k$. Note that it is $\texttt{0-indexed}$.

Perform $N$ operations to delete all elements of $a$. For each operation:

• Let the current length of $a$ be $n$.
• Let $S=\{0,k,2k,\cdots,k\lfloor\frac{n-1}{k}\rfloor\}$. Find $v=\max_{i\in S} a_i$.
• Let $p$ be $\min_{i\in S, a_i=v} i$.
• Delete $a_p$. The elements after it shift left by one position.

Output the number deleted in each operation.

Input Format

The first line contains two positive integers $N, k$.

The second line contains $N$ positive integers describing $a$.

Output Format

Output $N$ lines, each containing one integer: the number deleted in each operation.

10 2
2 3 1 9 10 4 5 6 1 5

10
6
4
5
2
9
3
5
1
1

10 3
2 3 1 9 10 4 5 6 1 5

9
10
4
5
6
2
5
3
1
1

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that:

• $2 \le k \le N \le 10^5$.
• $1 \le a_i \le N$.

Translated by ChatGPT 5