버블

$N$개의 항을 가진 수열 $A = \left[ A_1, A_2, \cdots, A_N \right]$이 있다. 수열의 인접한 항을 교환하는 작업을 최대 $K$번 수행하여 $A_N - A_1$의 값을 가장 크게 만들고 싶다.

$K$번 이하의 작업으로 만들 수 있는 $A_N - A_1$의 최댓값을 출력하는 프로그램을 작성하라.

입력 형식

첫 줄에 수열의 길이를 나타내는 정수 $N$과 교환 작업의 최대 횟수를 나타내는 정수 $K$가 주어진다. ($2 \le N \le 200\,000;$ $0 \le K \le 2N$)

그다음 줄에 수열의 $N$개의 항의 초깃값이 공백으로 구분되어 차례대로 주어진다. 이 값은 모두 $1$ 이상 $1\,000\,000\,000$ 이하의 정수다.

출력 형식

첫 줄에 만들 수 있는 $A_N - A_1$의 최댓값을 출력한다.

예제

5 2
3 2 1 5 2

3

예제 설명

예제에서, 첫 번째와 두 번째의 $3$과 $2$를 교환하면 수열은 $[2, 3, 1, 5, 2]$가 된다. 다시, 네 번째와 다섯 번째의 $5$와 $2$를 교환하면 수열은 $[2, 3, 1, 2, 5]$가 된다. 이 경우가 $A_N - A_1$을 가장 크게 만들 수 있는 방법이므로 답은 $3$이다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설