stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

const int N=2000;

int a[N+1];

int main(){

  int n,k,q;

  scanf("%d%d%d",&n,&k,&q); 

  for (int i=0;i<n;i++)

    scanf("%d",&a[i]);

  int ans=1e9;

  for (int& bound:a) {

    vector<int>t;

    vector<int>s;

    for (int i=0;i<=n;i++){

      if (i==n||a[i]<bound){

        sort(t.begin(),t.end());

        for (int i=0;i<=(int)t.size()-k;i++)

          s.push_back(t[i]);

        t.clear();

      }else t.push_back(a[i]);

    }

    if ((int)s.size()<q) continue;

    sort(s.begin(),s.end());

    ans=min(ans,s[q-1]-bound);

  }

  printf("%d\n",ans);

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.763796072037346x):
#include <iostream>

#include <vector>

#include <set>

#include <map>

#include <iomanip>

#include <random>

#include <unordered_set>

#include <algorithm>

#include <unordered_map>





using namespace std;





signed main() {

	ios::sync_with_stdio(false);

	cin.tie(0);

	int n, k, q;

	cin >> n >> k >> q;

	vector<int> a(n);

	for (int i = 0; i < n; i++) {

		cin >> a[i];

	}

	vector<int> b = a;

	sort(b.begin(), b.end());

	int ans = 1e9;

	for (int i = 0; i < b.size(); i++) {

		int l = -1, r = 1e9 + 2;

		while (r - l > 1) {

			int m = (l + r) / 2;

			int L = b[i];

			int R = b[i] + m;

			int col = 0;

			vector<int> sz = {0};

			vector<int> tt = {0};

			for (int i = 0; i < n; i++) {

				if (a[i] >= L) {

					sz[sz.size() - 1]++;

					if (a[i] <= R) {

						tt[tt.size() - 1]++;

					}

				}

				else {

					sz.push_back(0);

					tt.push_back(0);

				}

			}

			for (int i = 0; i < tt.size(); i++) {

				if (sz[i] >= k)

					col += min(sz[i] - k + 1, tt[i]);

			}

			if (col >= q)

				r = m;

			else

				l = m;

		}

		ans = min(ans, r);

	}

	cout << ans;

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

const int N=2000;

int a[N+1];

int main(){

  int n,k,q;

  scanf("%d%d%d",&n,&k,&q); 

  for (int i=0;i<n;i++)

    scanf("%d",&a[i]);

  int ans=1e9;

  for (int& bound:a) {

    vector<int>t;

    vector<int>s;

    for (int i=0;i<=n;i++){

      if (i==n||a[i]<bound){

        sort(t.begin(),t.end());

        for (int i=0;i<=(int)t.size()-k;i++)

          s.push_back(t[i]);

        t.clear();

      }else t.push_back(a[i]);

    }

    if ((int)s.size()<q) continue;

    sort(s.begin(),s.end());

    ans=min(ans,s[q-1]-bound);

  }

  printf("%d\n",ans);

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.945054986339294x):
#include<bits/stdc++.h>

using namespace std;

#define all(v) ((v).begin()),((v).end())

#define ll long long

#define fastIO cout << fixed << setprecision(12), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

double const EPS = 1e-12, PI = acos(-1);

const int N = 4e5 + 9, M = 5e3 + 9, OO = 1e9 + 7, MOD = 1e9 + 7;

const ll inf = 1e18;



int arr[N];



int main() {

  fastIO;

#ifdef LOCAL

  freopen("input.in", "rt", stdin);

#endif

  int n, k, q;

  cin >> n >> k >> q;

  for (int i = 0; i < n; ++i) {

    cin >> arr[i];

  }

  arr[n] = -1;

  int ans = OO + OO;

  for (int i = 0; i < n; ++i) {

    vector<int> vv, vv2;

    int cnt = 0;

    int lower = arr[i];

    for (int j = 0; j <= n; ++j) {

      if(arr[j] < lower) {

        if(cnt) {

          sort(vv2.begin(), vv2.end());

          for (int i = 0; i < cnt; ++i)

            vv.push_back(vv2[i]);

        }

        vv2.clear();

        cnt = 0;

      } else {

        vv2.push_back(arr[j]);

      }

      if((int)vv2.size() >= k)

        ++cnt;

    }

    if((int)vv.size() < q)

      continue;

    sort(vv.begin(), vv.end());

    ans = min(ans, vv[q - 1] - lower);

  }

  cout << ans;

  return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#include<vector>

#include<queue>

#include<stack>

#include<string>

#define INF 0x3f3f3f3f

using namespace std;

inline int read(){

    int w=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9'){

        w=(w<<3)+(w<<1)+ch-48;

        ch=getchar();

    }

    return w*f;

}

int n,m,q,a[200010],b[200010],ans,vec[20010];

priority_queue<int> pq;

inline void work(){

    while(!pq.empty()){

        if(pq.size()>=m){

            vec[0]++;vec[vec[0]]=-pq.top();

        }

        pq.pop();

    }

}

signed main(){

    n=read();m=read();q=read();ans=INF;

    for(int i=1;i<=n;i++)a[i]=read();

    for(int i=1;i<=n;i++){

        int now=a[i];

        for(int j=1;j<=n;j++){

            if(a[j]>=now) pq.push(-a[j]);

            else work();

        }

        work();

        if(vec[0]>=1){

            sort(vec+1,vec+vec[0]+1);

        }

        if(vec[0]>=q&&vec[1]==now){

            ans=min(ans,vec[q]-now);

        }

        memset(vec,0,sizeof(vec));

    }

    cout<<ans<<endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.1409640261163891x):
#include<bits/stdc++.h>

using namespace std;

#define all(v) ((v).begin()),((v).end())

#define ll long long

#define fastIO cout << fixed << setprecision(12), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

double const EPS = 1e-12, PI = acos(-1);

const int N = 4e5 + 9, M = 5e3 + 9, OO = 1e9 + 7, MOD = 1e9 + 7;

const ll inf = 1e18;



int arr[N];



int main() {

  fastIO;

#ifdef LOCAL

  freopen("input.in", "rt", stdin);

#endif

  int n, k, q;

  cin >> n >> k >> q;

  for (int i = 0; i < n; ++i) {

    cin >> arr[i];

  }

  arr[n] = -1;

  int ans = OO + OO;

  for (int i = 0; i < n; ++i) {

    vector<int> vv, vv2;

    int cnt = 0;

    int lower = arr[i];

    for (int j = 0; j <= n; ++j) {

      if(arr[j] < lower) {

        if(cnt) {

          sort(vv2.begin(), vv2.end());

          for (int i = 0; i < cnt; ++i)

            vv.push_back(vv2[i]);

        }

        vv2.clear();

        cnt = 0;

      } else {

        vv2.push_back(arr[j]);

      }

      if((int)vv2.size() >= k)

        ++cnt;

    }

    if((int)vv.size() < q)

      continue;

    sort(vv.begin(), vv.end());

    ans = min(ans, vv[q - 1] - lower);

  }

  cout << ans;

  return 0;

}
// Slower C++ solution:
#include <stdio.h>

#include <iostream>

#include <algorithm>

#define R register

#define MN 2005

typedef long long ll;

namespace IO{

	inline int read(){

		R int x; R bool f; R char c;

		for (f=0; (c=getchar())<'0'||c>'9'; f=c=='-');

		for (x=c^'0'; (c=getchar())>='0'&&c<='9'; x=(x<<1)+(x<<3)+(c^'0'));

		return f?-x:x;

	}

}

namespace sol{

	int n,k,q,vl[MN],seq[MN],ans=0x3f3f3f3f,vn,tmp[MN];

	void solve(int mi){

		vn=0;for (R int l=1,r; l<=n; l=r){

			for (;seq[l]<mi&&l<=n;++l);

			for (r=l;seq[r]>=mi&&r<=n;++r);

			if (r-l>=k){

				for (R int i=l; i<r; ++i)

					tmp[i-l]=seq[i];

				std::sort(tmp,tmp+r-l);

				for (R int i=0; i<r-l-k+1; ++i)

					vl[++vn]=tmp[i];

			}

		}

		if (vn<q) return;

		std::sort(vl+1,vl+vn+1);

		ans=std::min(ans,vl[q]-vl[1]);

	}

	void main(){

		n=IO::read(),k=IO::read(),q=IO::read();

		for (R int i=1; i<=n; ++i) seq[i]=IO::read();

		for (R int i=1; i<=n; ++i) solve(seq[i]);

		printf("%d\n",ans);

	}

}

int main(){sol::main();return 0;}

// Faster C++ solution for the same problem (measured speedup: 5.06672707574442x):
#include<cstdio>

#include<algorithm>

int n,k,q,mi;

int a[2010],b[2010],ans[2001],cn,Ans=2147483647;

int main(){

	scanf("%d%d%d",&n,&k,&q);

	for(int i=1;i<=n;i++) scanf("%d",&a[i]);

	for(int i=1;i<=n;i++){

		mi=a[i];

		int l=1,r=1;

		while(l<=n){

			while(a[l]<mi&&l<n) l++;

			r=l;

			while(a[r+1]>=mi&&r<n) r++;

			if(r-l+1>=k){

				for(int j=l;j<=r;j++) b[j]=a[j];

				std::sort(b+l,b+r+1);

				for(int j=l;j<=r-k+1;j++) ans[++cn]=b[j];

			}

			l=r+1;

		}

		std::sort(ans+1,ans+cn+1);

		if(cn>=q) if(ans[q]-ans[1]<Ans) Ans=ans[q]-ans[1];

		cn=0;

	}

	printf("%d\n",Ans);

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define F(i,a,b) for(int i=(a);i<=(b);++i)

#define F2(i,a,b) for(int i=(a);i<(b);++i)

#define dF(i,a,b) for(int i=(a);i>=(b);--i)

#define dF2(i,a,b) for(int i=(a);i>(b);--i)

#define dF3(i,a,b) for(int i=(a)-1;i>=(b);--i)

using namespace std;typedef long long ll;typedef double ld;int INF=0x3f3f3f3f;int INF2=0x7fffffff;ll LNF=0x3f3f3f3f3f3f3f3f;ll LNF2=0x7fffffffffffffff;



int n,k,q,Ans=INF;

int a[2001],p[2001],v[2001];

bool cmp(int i,int j){return a[i]<a[j];}

int siz[2001],bel[2001];

int check(){

	int S=0;

	F(i,1,n) bel[i]=0;

	F(i,1,n){

		if(!v[i]){

			if(v[i-1]) ++S, siz[S]=1;

			else ++siz[S];

			bel[i]=S;

		}

	}

	int cnt=0;

	int Amn=INF, Amx=-INF;

	F(i,1,n) if(!v[p[i]]){

		int pos=p[i];

		if(siz[bel[pos]]>=k) Amn=min(Amn,a[pos]), Amx=max(Amx,a[pos]), --siz[bel[pos]], ++cnt;

		if(cnt==q) break;

	}

	if(cnt!=q) return INF;

	else return Amx-Amn;

}

int main(){

	scanf("%d%d%d",&n,&k,&q);

	F(i,1,n) scanf("%d",a+i), p[i]=i;

	sort(p+1,p+n+1,cmp);

	v[0]=1;

	Ans=check();

	F(i,1,n){

		v[p[i]]=1;

		Ans=min(Ans,check());

	} printf("%d",Ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.088540549179744x):
#include<cstdio>

#include<algorithm>

int n,k,q,mi;

int a[2010],b[2010],ans[2001],cn,Ans=2147483647;

int main(){

	scanf("%d%d%d",&n,&k,&q);

	for(int i=1;i<=n;i++) scanf("%d",&a[i]);

	for(int i=1;i<=n;i++){

		mi=a[i];

		int l=1,r=1;

		while(l<=n){

			while(a[l]<mi&&l<n) l++;

			r=l;

			while(a[r+1]>=mi&&r<n) r++;

			if(r-l+1>=k){

				for(int j=l;j<=r;j++) b[j]=a[j];

				std::sort(b+l,b+r+1);

				for(int j=l;j<=r-k+1;j++) ans[++cn]=b[j];

			}

			l=r+1;

		}

		std::sort(ans+1,ans+cn+1);

		if(cn>=q) if(ans[q]-ans[1]<Ans) Ans=ans[q]-ans[1];

		cn=0;

	}

	printf("%d\n",Ans);

	return 0;

}
// Slower C++ solution:
#include <algorithm>

#include <iostream>

#include <cstdio>

#include <queue>



using namespace std ;



typedef long long LL ;



priority_queue<LL,deque<LL>,greater<LL> > h ;

priority_queue<LL,deque<LL>,greater<LL> > t ;

LL v[2333];

LL a[2333];

LL b[2333];

LL n , k , q ;

LL res;



int main ()

{

	LL i , j ;

	LL x , s ;

	res=9223372036854775807;

	scanf("%lld%lld%lld",&n,&k,&q);

	for ( i=1 ; i<=n ; i++ ) scanf("%lld",a+i),b[i]=a[i];

	sort(b+1,b+n+1);

	for ( s=1 ; s<=n ; s++ ) 

	{

		fill(v+1,v+n+1,0);

		while ( !h.empty() ) h.pop();

		x=b[s];

		LL m=0;

		for ( i=1 ; i<=n ; i++ )

			if ( a[i]<x ) v[++m]=i;

		v[++m]=n+1;

		for ( i=1 ; i<=m ; i++ )

		{

			if ( v[i]-v[i-1]-1<k ) continue;

			for ( j=v[i-1]+1 ; j<v[i] ; j++ ) t.push(a[j]);

			LL tmp=v[i]-v[i-1]-k;

			for ( j=1 ; j<=tmp ; j++ ) h.push(t.top()),t.pop();

			while ( !t.empty() ) t.pop();

		}

		for ( i=1 ; i<q ; i++ )	

		{

			if ( h.empty() ) goto end;

			h.pop();

		}

		if ( h.empty() ) goto end;

		res=min(res,h.top()-x);

		end:;

	}

	printf("%lld\n",res);

	return 0 ;

}

// Faster C++ solution for the same problem (measured speedup: 5.201630066014453x):
#include<cstdio>

#include<algorithm>

int n,k,q,mi;

int a[2010],b[2010],ans[2001],cn,Ans=2147483647;

int main(){

	scanf("%d%d%d",&n,&k,&q);

	for(int i=1;i<=n;i++) scanf("%d",&a[i]);

	for(int i=1;i<=n;i++){

		mi=a[i];

		int l=1,r=1;

		while(l<=n){

			while(a[l]<mi&&l<n) l++;

			r=l;

			while(a[r+1]>=mi&&r<n) r++;

			if(r-l+1>=k){

				for(int j=l;j<=r;j++) b[j]=a[j];

				std::sort(b+l,b+r+1);

				for(int j=l;j<=r-k+1;j++) ans[++cn]=b[j];

			}

			l=r+1;

		}

		std::sort(ans+1,ans+cn+1);

		if(cn>=q) if(ans[q]-ans[1]<Ans) Ans=ans[q]-ans[1];

		cn=0;

	}

	printf("%d\n",Ans);

	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

using namespace std;

int main() {

	int n,m,q,a[2005];

	scanf("%d%d%d",&n,&m,&q);

	for (register int i=1;i<=n;++i) {

		scanf("%d",a+i);

	}

	int l=0,r=2000000000;

	while (l<r) {

		int mid=(l+r)>>1;

		bool ok=0;

		for (register int i=1;i<=n;++i) {

			int p=a[i],k=0,tmp=0,cnt=0;

			for (register int j=1;j<=n+1;++j) {

				if (a[j]<p||j==n+1) {

					tmp+=j-k-1<m?0:min(j-k-1-m+1,j-k-1-cnt);

					k=j;

					cnt=0;

				}

				else if (a[j]>p+mid) {

					++cnt;

				}

			}

			if (tmp>=q) {

				ok=1;

				break;

			}

		}

		ok?r=mid:l=mid+1;

	}

	printf("%d",l);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.118073428839263x):
#include<cstdio>

#include<algorithm>

using namespace std;

#define mx 200005

inline int min(int x,int y){return x<y?x:y;}

inline int max(int x,int y){return x>y?x:y;}

int n,k,q,qz[mx],qp[mx],ans=2e9+5;

inline bool ck(int kl,int kr)

{

	int nl=0,nw=0,res=0;

	for(int i=1;i<=n;++i)

	{

		if(qz[i]>=kl&&qz[i]<=kr) ++nl,++nw;

		else if(qz[i]>kr) ++nl;

		else res+=max(0,min(nl-k+1,nw)),nl=nw=0;

	}

	res+=max(0,min(nl-k+1,nw)),nl=nw=0;

	return res>=q;

}

int main()

{

	scanf("%d%d%d",&n,&k,&q);

	for(int i=1;i<=n;++i)

		scanf("%d",&qz[i]),qp[i]=qz[i];

	sort(qp+1,qp+n+1);

	for(int i=1;i<=n;++i)

	{

		int l=i,r=n,mid;

		while(l<=r)

		{

			mid=(l+r)/2;

			if(ck(qp[i],qp[mid])) ans=min(ans,qp[mid]-qp[i]),r=mid-1;

			else l=mid+1;

		}

	}

	printf("%d",ans);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



#define fi first

#define se second

#define sz(x) ((int)x.size())

using namespace std;

typedef long long lli;

typedef pair<int,int> pii;



const int inf=1e9;

int n,k,q,arr[2000];

pii a[2000];

int get(int val) {

	int mx=0;

	priority_queue<int,vector<int>,greater<int>> aq,qq;

	for(int i=0;i<n;i++) if(arr[i]>=val) {

		int j=i;

		while(!aq.empty()) aq.pop();

		for(;j<n && arr[j]>=val;j++) aq.push(arr[j]);

		

		int s=sz(aq)-k+1;

		while(s>0) {

			qq.push(aq.top()); aq.pop();

			s--;

		}

		i=j-1;

	}

	if(sz(qq)<q) return inf;

	for(int i=0;i<q;i++) {

		mx=qq.top(); qq.pop();

	}

	return mx-val;

}

int main() {

	scanf("%d%d%d",&n,&k,&q);

	for(int i=0;i<n;i++) {

		scanf("%d",arr+i);

		a[i].fi=arr[i]; a[i].se=i;

	}

	sort(a,a+n);

	

	int ans=inf;

	for(int i=0;i<n;i++) if(i==0 || a[i].fi!=a[i-1].fi)

		ans=min(ans,get(a[i].fi));



	printf("%d\n",ans);

	

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.1735903985057945x):
#include<cstdio>

#include<algorithm>

using namespace std;

#define mx 200005

inline int min(int x,int y){return x<y?x:y;}

inline int max(int x,int y){return x>y?x:y;}

int n,k,q,qz[mx],qp[mx],ans=2e9+5;

inline bool ck(int kl,int kr)

{

	int nl=0,nw=0,res=0;

	for(int i=1;i<=n;++i)

	{

		if(qz[i]>=kl&&qz[i]<=kr) ++nl,++nw;

		else if(qz[i]>kr) ++nl;

		else res+=max(0,min(nl-k+1,nw)),nl=nw=0;

	}

	res+=max(0,min(nl-k+1,nw)),nl=nw=0;

	return res>=q;

}

int main()

{

	scanf("%d%d%d",&n,&k,&q);

	for(int i=1;i<=n;++i)

		scanf("%d",&qz[i]),qp[i]=qz[i];

	sort(qp+1,qp+n+1);

	for(int i=1;i<=n;++i)

	{

		int l=i,r=n,mid;

		while(l<=r)

		{

			mid=(l+r)/2;

			if(ck(qp[i],qp[mid])) ans=min(ans,qp[mid]-qp[i]),r=mid-1;

			else l=mid+1;

		}

	}

	printf("%d",ans);

	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

using namespace std;

int main() {

	int n,m,q,a[2005];

	scanf("%d%d%d",&n,&m,&q);

	for (register int i=1;i<=n;++i) {

		scanf("%d",a+i);

	}

	int l=0,r=2000000000;

	while (l<r) {

		int mid=(l+r)>>1;

		bool ok=0;

		for (register int i=1;i<=n;++i) {

			int p=a[i],k=0,tmp=0,cnt=0;

			for (register int j=1;j<=n+1;++j) {

				if (a[j]<p||j==n+1) {

					tmp+=j-k-1<m?0:min(j-k-1-m+1,j-k-1-cnt);

					k=j;

					cnt=0;

				}

				else if (a[j]>p+mid) {

					++cnt;

				}

			}

			if (tmp>=q) {

				ok=1;

				break;

			}

		}

		ok?r=mid:l=mid+1;

	}

	printf("%d",l);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.2836899026440263x):
#include<cstdio>

#include<cstring>

#include<algorithm>

const int N=2003,INF=0x3f3f3f3f,D=1<<11;

int n,m,q,a[N],p[N],ans=INF;

#define M (L+R>>1)

struct segment_tree{

	int mn[1<<12],mx[1<<12],s[1<<12];

	segment_tree(){memset(mn,63,sizeof mn);}

	int Min(int l,int r){

		int res=n+1;

		if(l>r)return res;

		for(l=l+D-1,r=r+D+1;l^r^1;l>>=1,r>>=1){

		  if(~l&1)res=std::min(res,mn[l^1]);

		  if( r&1)res=std::min(res,mn[r^1]);

		}return res;

	}

	int Max(int l,int r){

		int res=0;

		if(l>r)return res;

		for(l=l+D-1,r=r+D+1;l^r^1;l>>=1,r>>=1){

		  if(~l&1)res=std::max(res,mx[l^1]);

		  if( r&1)res=std::max(res,mx[r^1]);

		}return res;

	}

	int Count(int l,int r){

		int res=0;

		if(l>r)return res;

		for(l=l+D-1,r=r+D+1;l^r^1;l>>=1,r>>=1){

		  if(~l&1)res+=s[l^1];

		  if( r&1)res+=s[r^1];

		}return res;

	}

	void Update(int k,int a){

		for(k+=D,mn[k]=mx[k]=a,k>>=1;k;k>>=1)

		  mn[k]=std::min(mn[k<<1],mn[k<<1|1]),

		  mx[k]=std::max(mx[k<<1],mx[k<<1|1]);

	}

	void Erase(int k){

		for(k+=D,s[k]=1,k>>=1;k;k>>=1)

		  s[k]=s[k<<1]+s[k<<1|1];

	}

}f,g;

bool Cmp(const int&i,const int&j){return a[i]<a[j];}

int main(){

	int mn,mx,l,r;

	scanf("%d%d%d",&n,&m,&q);

	for(int i=1;i<=n;i++)scanf("%d",a+i),p[i]=i;

	std::sort(p+1,p+1+n,Cmp);

	for(int j=1,i,jj;j<=n;j++){

	  i=p[j];jj=j;

	  g=f;mx=0,mn=INF;

	  for(int k=1;k<=q;k++){

		for(;jj<=n&&(r=g.Min(p[jj]+1,n),l=g.Max(1,p[jj]-1),r-l-g.Count(l+1,r-1)<=m);jj++);

		if(jj>n)goto Brk;

		mx=std::max(mx,a[p[jj]]);

		mn=std::min(mn,a[p[jj]]);

		g.Erase(p[jj]);jj++;

	  }

	  ans=std::min(ans,mx-mn);

	  Brk:;

	  f.Update(i,i);

	}printf("%d",ans);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



#define fi first

#define se second

#define sz(x) ((int)x.size())

using namespace std;

typedef long long lli;

typedef pair<int,int> pii;



const int inf=1e9;

int n,k,q,arr[2000];

pii a[2000];

int get(int val) {

	int mx=0;

	priority_queue<int,vector<int>,greater<int>> aq,qq;

	for(int i=0;i<n;i++) if(arr[i]>=val) {

		int j=i;

		while(!aq.empty()) aq.pop();

		for(;j<n && arr[j]>=val;j++) aq.push(arr[j]);

		

		int s=sz(aq)-k+1;

		while(s>0) {

			qq.push(aq.top()); aq.pop();

			s--;

		}

		i=j-1;

	}

	if(sz(qq)<q) return inf;

	for(int i=0;i<q;i++) {

		mx=qq.top(); qq.pop();

	}

	return mx-val;

}

int main() {

	scanf("%d%d%d",&n,&k,&q);

	for(int i=0;i<n;i++) {

		scanf("%d",arr+i);

		a[i].fi=arr[i]; a[i].se=i;

	}

	sort(a,a+n);

	

	int ans=inf;

	for(int i=0;i<n;i++) if(i==0 || a[i].fi!=a[i-1].fi)

		ans=min(ans,get(a[i].fi));



	printf("%d\n",ans);

	

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.2976143948142147x):
#include<cstdio>

#include<cstring>

#include<algorithm>

const int N=2003,INF=0x3f3f3f3f,D=1<<11;

int n,m,q,a[N],p[N],ans=INF;

#define M (L+R>>1)

struct segment_tree{

	int mn[1<<12],mx[1<<12],s[1<<12];

	segment_tree(){memset(mn,63,sizeof mn);}

	int Min(int l,int r){

		int res=n+1;

		if(l>r)return res;

		for(l=l+D-1,r=r+D+1;l^r^1;l>>=1,r>>=1){

		  if(~l&1)res=std::min(res,mn[l^1]);

		  if( r&1)res=std::min(res,mn[r^1]);

		}return res;

	}

	int Max(int l,int r){

		int res=0;

		if(l>r)return res;

		for(l=l+D-1,r=r+D+1;l^r^1;l>>=1,r>>=1){

		  if(~l&1)res=std::max(res,mx[l^1]);

		  if( r&1)res=std::max(res,mx[r^1]);

		}return res;

	}

	int Count(int l,int r){

		int res=0;

		if(l>r)return res;

		for(l=l+D-1,r=r+D+1;l^r^1;l>>=1,r>>=1){

		  if(~l&1)res+=s[l^1];

		  if( r&1)res+=s[r^1];

		}return res;

	}

	void Update(int k,int a){

		for(k+=D,mn[k]=mx[k]=a,k>>=1;k;k>>=1)

		  mn[k]=std::min(mn[k<<1],mn[k<<1|1]),

		  mx[k]=std::max(mx[k<<1],mx[k<<1|1]);

	}

	void Erase(int k){

		for(k+=D,s[k]=1,k>>=1;k;k>>=1)

		  s[k]=s[k<<1]+s[k<<1|1];

	}

}f,g;

bool Cmp(const int&i,const int&j){return a[i]<a[j];}

int main(){

	int mn,mx,l,r;

	scanf("%d%d%d",&n,&m,&q);

	for(int i=1;i<=n;i++)scanf("%d",a+i),p[i]=i;

	std::sort(p+1,p+1+n,Cmp);

	for(int j=1,i,jj;j<=n;j++){

	  i=p[j];jj=j;

	  g=f;mx=0,mn=INF;

	  for(int k=1;k<=q;k++){

		for(;jj<=n&&(r=g.Min(p[jj]+1,n),l=g.Max(1,p[jj]-1),r-l-g.Count(l+1,r-1)<=m);jj++);

		if(jj>n)goto Brk;

		mx=std::max(mx,a[p[jj]]);

		mn=std::min(mn,a[p[jj]]);

		g.Erase(p[jj]);jj++;

	  }

	  ans=std::min(ans,mx-mn);

	  Brk:;

	  f.Update(i,i);

	}printf("%d",ans);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define len(x) (int) (x.size())

using namespace std;

typedef long long ll;



int main(){

    int n, k;

    string s;

    cin >> n >> k >> s;



    s[k-1] = s[k-1]+32;

    cout << s << '\n'; 

    

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.27325667279165x):
#include <stdio.h>



int main(){

	char string[55];

	int a, b;

	scanf("%d %d", &a, &b);

	getchar();

	scanf("%[^\n]", &string);

	string[b-1] +=  32;

	printf("%s", string);

	

	

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define len(x) (int) (x.size())

using namespace std;

typedef long long ll;



int main(){

    int n, k;

    string s;

    cin >> n >> k >> s;



    s[k-1] = s[k-1]+32;

    cout << s << '\n'; 

    

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.287129371253986x):
#include <stdio.h>



int main () {

	int panjang;

	int kecil;

	char abc[52];

	

	scanf("%d %d", &panjang, &kecil);

	kecil--;

	scanf("%s", &abc);

	abc[kecil] = abc[kecil] + 32;

	printf("%s", abc);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define len(x) (int) (x.size())

using namespace std;

typedef long long ll;



int main(){

    int n, k;

    string s;

    cin >> n >> k >> s;



    s[k-1] = s[k-1]+32;

    cout << s << '\n'; 

    

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.285191421507967x):
#include <stdio.h>



int main() {

	int input1;

	int input2;

	char input3[102];

	

	scanf("%d %d", &input1, &input2);

	scanf("%s", input3);

	

	input3[input2-1] = input3[input2-1] + 32;

	

	printf("%s", input3);

	

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define len(x) (int) (x.size())

using namespace std;

typedef long long ll;



int main(){

    int n, k;

    string s;

    cin >> n >> k >> s;



    s[k-1] = s[k-1]+32;

    cout << s << '\n'; 

    

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.281959378187379x):
#include <stdio.h>



int main() {

	char word[53];

	int lgth, num;

	scanf("%d %d\n", &lgth, &num);

	scanf("%s", word);

	

	num--;

	word[num] += 32;

	printf("%s", word);

	

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define len(x) (int) (x.size())

using namespace std;

typedef long long ll;



int main(){

    int n, k;

    string s;

    cin >> n >> k >> s;



    s[k-1] = s[k-1]+32;

    cout << s << '\n'; 

    

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.278053740251729x):
#include <stdio.h>



int main() {

	int N, K;

	scanf("%d %d", &N, &K);

	getchar();

	char S[N];

	scanf("%s", &S);

	S[K-1] += 32;

	printf("%s", S);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define len(x) (int) (x.size())

using namespace std;

typedef long long ll;



int main(){

    int n, k;

    string s;

    cin >> n >> k >> s;



    s[k-1] = s[k-1]+32;

    cout << s << '\n'; 

    

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.275882186620891x):
#include<stdio.h>



int main() {

	char S[100];

	int N,K;

	scanf("%d %d",&N,&K);

	scanf("%s",S);

	S[K-1] += 32;

	printf("%s\n",S);





	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define len(x) (int) (x.size())

using namespace std;

typedef long long ll;



int main(){

    int n, k;

    string s;

    cin >> n >> k >> s;



    s[k-1] = s[k-1]+32;

    cout << s << '\n'; 

    

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.287284976745651x):
#include <stdio.h>



int main(){

	int panjangkata,kecilin;

	scanf("%d %d", &panjangkata,&kecilin);

	char huruf[panjangkata+5];

	scanf("%s",huruf);

	huruf[kecilin-1] += 32;

	printf("%s",huruf);

	

    return 0;

}