409997: GYM103895 G Carrot Thief

Remi the rabbit is really a refined robber, randomly ransacking real ranches regarding their rotund roots.

Remi is planning her largest heist yet! There are $$$n$$$ farms in a line from which she plans to steal carrots from. In the dead of night, she plans to visit some of the farms, eating the carrots along the way to nourish her for the rest of the heist.

Each of the farms has an associated carrot quality, $$$a_i$$$. Regardless of which farm they are from, all carrots have a nourishment value of $$$k$$$, meaning that if Remi eats carrots from farm $$$i$$$, she has enough energy to visit farms $$$i+1 \ldots i+k$$$. Remi starts out with enough energy to visit farms $$$1 \ldots k$$$.

Remi is looking to only eat the highest quality carrots, and would like to maximize the quality of the worst carrot she must eat to pass farm $$$n$$$. Can you help her?

The first line contains two integers, $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 10^3$$$).

The next line contains $$$n$$$ integers, $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), where $$$a_i$$$ represents the quality of the carrots on farm $$$i$$$.

Output a single integer, the maximum value of the lowest quality carrot Remi must eat to get past all $$$n$$$ farms.

5 3
3 2 5 1 4

5

5 3
4 5 2 1 3

3