409997: GYM103895 G Carrot Thief

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Carrot Thieftime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

Input

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

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

ExamplesInput
5 3
3 2 5 1 4
Output
5
Input
5 3
4 5 2 1 3
Output
3

加入题单

上一题 下一题 算法标签: