410033: GYM103921 E It's Raining Rocks!

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.

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 a single number, the minimal basket width needed to collect all the rocks.

4 2
6 1 4 5

3