P14665 Sequence Problem

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$.

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

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

### 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.  | Subtask | $n \le$ | $m \le$ | Special Properties | Score | Dependencies | |:-----:|:-----:|:-----:|:-----:|:-----:|:-----:| | $1$ | $10$ | $10$ | none | $10$ | none | | $2$ | $100$ | $100$ | none | $20$ | $1$ | | $3$ | $500$ | $500$ | none | $25$ | $1,2$ | | $4$ | $5 \times 10^3$ | $5 \times 10^3$ | A | $5$ | none | | $5$ | $5 \times 10^3$ | $5 \times 10^3$ | none | $40$ | $1,2,3,4$ | 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.