Closet

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

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

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

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

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

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

첫 번째 줄에 두 정수 $N$과 $M$이 주어진다.

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

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

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

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