题目描述

一条笔直的铁路上有 N 个车站，坐标依次为 A1​<A2​<⋯<AN​。你要从第 1 站走到第 N 站，最多只能在中途停靠 K 次。为了准时到达，你需要保证相邻两次停靠的距离尽可能均匀。求能满足要求的最小最大行走距离。

输入格式

第一行两个整数 N,K。第二行 N 个整数 A1​,…,AN​。

输出格式

一个整数.

数据范围 2≤N≤10^5 0≤K≤N−2 1≤Ai​≤10^9

样例

5 2
1 3 5 7 11

2