Taein has a closet with $N$ clothes hanging in it. Currently, the $i$-th clothes from the left has color $c_i$.

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

However, organizing the closet into a beautiful state is quite tedious. So, Taein decided to remove at most $M$ clothes from the closet to make the remaining clothes almost 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 clothes from the left. Taein decided to recognize two adjacent clothes as the same color if the difference in color between them is at most $x$. In other words, the closet is called almost beautiful if there exists an integer $k$ ($1 \le k \le L$) for which the following holds:

• $d_j - d_{j+1} \leq x$ for each integer $j$ such that $1 \leq j < k$.
• $d_{j+1} - d_j \leq x$ for each integer $j$ such that $k \leq j < L$.

Let's find the smallest value of non-negative integer $x$ that can make the closet almost beautiful by removing $M$ or fewer clothes.

Input

The first line contains two integers $N$ and $M$ separated by a space.

The second line contains $N$ integers $c_1, c_2, \ldots, c_N$ separated by a space.

Output

Print the smallest value of $x$ ($x \ge 0$) that can make the closet almost beautiful.

Subtasks

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

Subtask 1 (4 points)

$M=0$

Subtask 2 (21 points)

$1 \leq N \leq 1\,000$

Subtask 3 (16 points)

$1 \leq c_i \leq 100$ ($1 \leq i \leq N$)

Subtask 4 (59 points)

No additional constraints.

Examples

Input 1

10 2
4 2 7 15 3 11 12 10 2 6

Output 1

2

Note

When $x=2$, Taein can make the closet almost beautiful by removing the 5th and 9th clothes from the left. There are no smaller values of $x$ which make it possible to make the closet almost beautiful.