수열 매끄럽게 만들기

길이 $N$의 정수 수열 $A_1, A_2, \cdots, A_N$이 주어진다.

최대 $K$개의 위치를 골라, 그 위치의 값을 임의의 정수로 바꿀 수 있다. 변경한 뒤의 수열을 $B_1, B_2, \cdots, B_N$이라 하자.

$N \ge 2$일 때 수열의 인접 차이를 다음과 같이 정의한다.

$N=1$일 때 인접 차이는 $0$으로 정의한다.

가능한 변경을 한 뒤 인접 차이의 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 한 줄에 가능한 인접 차이의 최솟값을 출력한다.

• $1 \le T \le 200\,000$.
• $1 \le N \le 200\,000$.
• $0\le K\le$.