P9044 [PA 2021] Koszulki

$n$ people take part in a contest, where the score of person $i$ is $a_i$. The organizers decide to give out at least $k$ gifts. However, if $\exist 1 \leq x, y \leq n, a_x \geq a_y$ and $x$ does not receive a gift but $y$ receives a gift, then $x$ will be unhappy. The organizers want everyone to be satisfied. Find the minimum number of gifts that must be given out.

The first line contains two integers $n, k$. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$.

One line containing one integer, which is the required value.

#### Explanation for Sample #1 The best plan is to give gifts to everyone except the last person. #### Constraints For $100\%$ of the testdata, $1 \leq k \leq n \leq 2 \times 10^3$, $1 \leq a_i \leq 120$. Translated by ChatGPT 5