25727번 - Building Bombing 다국어

KAIST has a series of $N$ buildings in a row, numbered from $1$ to $N$, from left to right. Building $i$ has a height of $h_i$. Building $i$ is visible from the left if and only if every building on its left has a height strictly less than $h_i$.

Your lab is located in building number $L$. Since your favorite number is $K$, you want to make your lab building the $K$-th tallest building visible from the left. To achieve your goal, you will blow up some of the buildings.

For example, suppose there are $N=7$ buildings in a row and their heights are $[10,30,90,40,60,60,80]$. Your lab is located at building number $L=2$ and your favorite number is $K=3$. After blowing up buildings $3$ and $7$, the buildings visible from the left will be buildings $1$, $2$, $4$, and $5$. Then your lab becomes the $3$rd tallest building visible from the left, as desired.

What is the minimum number of buildings to blow up to make your lab building the $K$-th tallest building visible from the left?

The first line contains three space-separated integers $N$, $L$, and $K$.

The second line contains $N$ space-separated integers $h_1,\dots ,h_N$.

Output the minimum number of buildings to blow up to make your lab building the $K$-th tallest building visible from the left. If it is impossible to do so, output $-1$ instead.

• $1\le L\le N\le 100\, 000$
• $1\le K\le 10$
• $1\le h_i\le 10^9$ $(1\le i\le N)$