#include<bits/stdc++.h>
using namespace std;
struct node{
	long long mx,mn;
	node(){
		mx=-1,mn=-114514191;
	}
};
node f[1001][501][2];
long long a[100001];
int n,m;
node nmin(node a,node b){
	if((a.mx-a.mn)<(b.mx-b.mn))return a;
	else return b;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(register int i=1;i<=n;i++)cin>>a[i];
	for(register int i=1;i<=n;i++)
		for(register int j=0;j<=m;j++){
			f[i][j][0]=nmin(f[i-1][j][0],f[i-1][j][1]);
			if(j==0||j*2-1>i)continue;
			f[i][j][1]=f[i-1][j-1][0];
			if(a[i]<f[i][j][1].mn||f[i][j][1].mn==-114514191)f[i][j][1].mn=a[i];
			if(a[i]>f[i][j][1].mx||f[i][j][1].mx==-1)f[i][j][1].mx=a[i];
		//	cout<<i<<" "<<j<<" "<<f[i][j][0].mx<<" "<<f[i][j][0].mn<<" "<<f[i][j][1].mx<<" "<<f[i][j][1].mn<<"\n";
		}
	cout<<min((f[n][m][1].mx-f[n][m][1].mn),(f[n][m][0].mx-f[n][m][0].mn));
}

想打 76 分，结果 12/kk