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
| Name |
|---|


