Description

Given a sequence $a$ of $n$ positive integers. Now you can perform one of the following operations up to $m$ times:

• Increase each number in the range $[l,r]$ by $1$.
• Decrease each number in the range $[l,r]$ by $1$.

You can independently select $l$ and $r$ in each operation.

Let $x$ be the maximum value of the sequence, and $y$ be the minimum value after the operations.

Find the minimum possible value of $x-y$.

Input Format

The first line contains two integers, $n$ and $m$.

The second line has $n$ numbers, and the $i$-$\text{th}$ number is $a_i$.

Output Format

One single number, the minimum possible value of $x-y$.

5 2
1 2 3 4 5

2

Hint

Example explanation

We can increase each number in $[1,4]$ and $[1,3]$ by $1$ to make the sequence $3,4,5,5,5$, $x-y=5-3=2$. It can be proven that no better solution exists.

Data Volume and Conventions

This problem is divided into subtasks. Your score in a subtask is the minimum score across all its test cases.

This problem uses subtask dependencies. You will not receive the score for a subtask unless you achieve full points on all its dependent subtasks.

Special property A: $\forall i \in [1,n),a_i=a_{i+1}$.

For all of the cases, $1 \le a_i \le n \le 5 \times 10^3$.

Bonus: $1 \le n,m \le 2 \times 10^5$. Contestants who have solved all problems (AK) are welcome to continue exploring.