Closet

Taein's closet has $N$ clothes hanging in a row. The color of the $i$-th piece from the left is $c_i$.

Taein considers the closet beautiful if there is an integer $k$ ($1 \le k \le N$) such that $c_1 \le c_2 \le \cdots \le c_k \ge c_{k+1} \ge \cdots \ge c_N$.

Arranging the closet into a beautiful state is quite a hassle. So Taein decided to remove at most $M$ clothes from the closet so that the remaining clothes become nearly beautiful.

After removing at most $M$ clothes, let $L$ be the number of remaining clothes and let $d_j$ be the color of the $j$-th piece from the left. Taein treats two adjacent pieces as the same color if their color difference is at most $x$. The closet is nearly beautiful if there is an integer $k$ ($1 \le k \le L$) such that the following hold.

• $d_j - d_{j+1} \le x$ for every integer $j$ with $1 \le j < k$.
• $d_{j+1} - d_j \le x$ for every integer $j$ with $k \le j < L$.

Find the smallest non-negative integer $x$ such that the closet can be made nearly beautiful by removing at most $M$ clothes.

The first line contains two integers $N$ and $M$. The second line contains $N$ integers $c_1, c_2, \ldots, c_N$, separated by spaces.

Print the smallest $x$ ($x \ge 0$) such that the closet can be made nearly beautiful.

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

When $x=2$, removing the 5th and 9th pieces from the left makes the closet nearly beautiful. No smaller $x$ can make the closet nearly beautiful.