옷장

태인이의 옷장에는 $N$개의 옷이 일렬로 걸려 있다. 왼쪽에서 $i$번째 옷의 색은 $c_i$이다.

태인이는 어떤 정수 $k$ ($1 \le k \le N$)가 존재하여 $c_1 \le c_2 \le \cdots \le c_k \ge c_{k+1} \ge \cdots \ge c_N$을 만족하면 옷장이 아름답다고 생각한다.

옷장을 아름다운 상태로 정리하는 것은 꽤 번거롭다. 그래서 태인이는 옷장에서 최대 $M$개의 옷을 제거해 남은 옷들을 거의 아름다운 상태로 만들기로 했다.

최대 $M$개의 옷을 제거한 후 남은 옷의 개수를 $L$, 왼쪽에서 $j$번째 옷의 색을 $d_j$라 하자. 태인이는 인접한 두 옷의 색 차이가 $x$ 이하이면 두 옷을 같은 색으로 본다. 다음을 만족하는 정수 $k$ ($1 \le k \le L$)가 존재하면 옷장이 거의 아름다운 상태이다.

• $1 \le j < k$인 모든 정수 $j$에 대해 $d_j - d_{j+1} \le x$.
• $k \le j < L$인 모든 정수 $j$에 대해 $d_{j+1} - d_j \le x$.

최대 $M$개 이하의 옷을 제거해 옷장을 거의 아름다운 상태로 만들 수 있는 가장 작은 음이 아닌 정수 $x$를 구하라.

첫 번째 줄에 두 정수 $N$과 $M$이 주어진다. 두 번째 줄에는 $N$개의 정수 $c_1, c_2, \ldots, c_N$이 공백을 사이에 두고 주어진다.

옷장을 거의 아름다운 상태로 만들 수 있는 가장 작은 $x$ ($x \ge 0$)의 값을 출력한다.

• $1 \le N \le 10^5$
• $0 \le M \le N$
• $1 \le c_i \le 10^9$ ($1 \le i \le N$)

$x=2$일 때, 왼쪽에서 5번째 옷과 9번째 옷을 제거하면 옷장은 거의 아름다운 상태가 된다. 이보다 더 작은 $x$로는 옷장을 거의 아름다운 상태로 만들 수 없다.