410027: GYM103920 E It's Raining Rocks!

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

Description

E. It's Raining Rocks!time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

It's raining rocks! Hallelujah!

It's raining rocks, every type of rock!

Pyroclastic, metamorphic, lustrous, and igneous!

Coarse and silty and sedimentary and porous!

Specifically, it's raining rocks in $$$N$$$ very specific locations along a line, where the $$$l_i$$$ is the $$$i$$$-th location. Before the weather event, you want to set up a system to collect these rocks to avoid catastrophic landslides. You plan to lay out some baskets where the rocks will fall, to keep them contained.

A basket of width $$$w$$$ can capture rocks from $$$w$$$ consecutive locations. You have commissioned $$$K$$$ baskets with the same width, but you still need to figure out how wide the baskets should be.

Given the locations of rock-rain, $$$l_i$$$ and the number of commissioned baskets, determine the minimal width the baskets should be to capture every falling rock.

Input

The first line contains two integers, $$$1 \leq N \leq 10^5$$$ and $$$1 \leq K \leq 10^5$$$.

The second line contains $$$N$$$ integers, $$$1 \leq l_i \leq 10^9$$$

Output

Output a single number, the minimal basket width needed to collect all the rocks.

ExampleInput
4 2
6 1 4 5
Output
3

加入题单

上一题 下一题 算法标签: