AtCoder Regular Contest 098 - Range Minimum Queries

You are given an integer sequence A of length N and an integer K.
You will perform the following operation on this sequence Q times:
 - Choose a contiguous subsequence of length K, then remove the smallest element among the K elements contained in the chosen subsequence (if there are multiple such elements, choose one of them as you like).
Let X and Y be the values of the largest and smallest element removed in the Q operations. You would like X-Y to be as small as possible.
Find the smallest possible value of X-Y when the Q operations are performed optimally.

-----Constraints-----
 - 1 \leq N \leq 2000
 - 1 \leq K \leq N
 - 1 \leq Q \leq N-K+1
 - 1 \leq A_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K Q
A_1 A_2 ... A_N

-----Output-----
Print the smallest possible value of X-Y.

-----Sample Input-----
5 3 2
4 3 1 5 2

-----Sample Output-----
1

In the first operation, whichever contiguous subsequence of length 3 we choose, the minimum element in it is 1.
Thus, the first operation removes A_3=1 and now we have A=(4,3,5,2).
In the second operation, it is optimal to choose (A_2,A_3,A_4)=(3,5,2) as the contiguous subsequence of length 3 and remove A_4=2.
In this case, the largest element removed is 2, and the smallest is 1, so their difference is 2-1=1.

Difficulty: HARD

Starter code:

Solutions:
import sys
input = sys.stdin.readline
(N, K, Q) = map(int, input().split())
a = list(map(int, input().split()))
ta = a + []
res = pow(10, 10)
bs = pow(10, 10)
for x in sorted(set(a)):
	t = [[]]
	for i in range(N):
		if ta[i] == bs:
			if t[-1] != []:
				t.append([])
		else:
			t[-1].append(a[i])
	tt = []
	for i in range(len(t)):
		t[i].sort()
		for j in range(len(t[i]) - K + 1):
			tt.append(t[i][j])
	if len(tt) < Q:
		break
	tt.sort()
	res = min(res, tt[Q - 1] - tt[0])
	for i in range(N):
		if a[i] == x:
			ta[i] = bs
print(res)


inf = float('inf')
(N, K, Q) = map(int, input().split())
a = tuple(map(int, input().split()))
ans = inf
for ma in sorted(set(a)):
	res = []
	seq = 0
	for (i, aa) in enumerate(a):
		if aa >= ma:
			seq += 1
		else:
			if seq >= K:
				res.extend(sorted(a[i - seq:i])[:seq - K + 1])
			seq = 0
	if seq >= K:
		res.extend(list(sorted(a[-seq:]))[:seq - K + 1])
	seq = 0
	if len(res) < Q:
		continue
	res.sort()
	ans = min(ans, res[Q - 1] - ma)
print(ans)


def solve(n, k, q, a):
	sorted_pairs = [(ai, i) for (i, ai) in enumerate(a)]
	sorted_pairs.sort()
	ans = 10 ** 10
	segments = [(0, n)]
	ly = 0
	for i in range(n - q + 1):
		(y, _) = sorted_pairs[i]
		if y == ly:
			continue
		ly = y
		b = []
		for (left, right) in segments:
			if k <= right - left:
				c = a[left:right].copy()
				c.sort()
				b += c[:right - left - k + 1]
		if q <= len(b):
			b.sort()
			x = b[q - 1]
			ans = min(ans, x - y)
		i_end = n - q + 1
		for i2 in range(i + 1, n - q + 1):
			if sorted_pairs[i2][0] != y:
				i_end = i2
				break
		for i2 in range(i, i_end):
			(_, j) = sorted_pairs[i2]
			for (h, seg) in enumerate(segments):
				(left, right) = seg
				if left <= j and j < right:
					segments.pop(h)
					segments.append((left, j))
					segments.append((j + 1, right))
					break
	return ans

def main():
	(n, k, q) = input().split()
	n = int(n)
	k = int(k)
	q = int(q)
	a = list(map(int, input().split()))
	print(solve(n, k, q, a))
main()


from itertools import *
(N, K, Q, *A) = map(int, open(0).read().split())
s = sorted
print(min(((s(sum((v[:max(0, len(v) - K + 1)] for v in (k * s(v) for (k, v) in groupby(A, lambda a: a >= Y))), []))[Q - 1:] + [2000000000.0])[0] - Y for Y in A)))


from itertools import *
(N, K, Q, *A) = map(int, open(0).read().split())
l = len
s = sorted
a = 1000000000.0
for Y in set(A):
	C = s(sum((v[:l(v) - K + 1] for v in (s(v) for (k, v) in groupby(A, lambda a: a >= Y) if k) if l(v) >= K), []))
	if l(C) >= Q:
		a = min(a, C[Q - 1] - Y)
print(a)


(n, k, q) = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = 10 ** 10
for y in a:
	li = []
	l = 0
	cnd = []
	l_cnd = 0
	for x in a + [-1]:
		if x < y:
			if l - k + 1 >= 0:
				li.sort()
				cnd += li[:l - k + 1]
				l_cnd += l - k + 1
			li = []
			l = 0
		else:
			li.append(x)
			l += 1
	if l_cnd >= q:
		cnd.sort()
		sub = cnd[q - 1] - y
		ans = min(ans, sub)
print(ans)


def main(n, k, q, x):
	ret = float('inf')
	for xi in x:
		c = []
		tmp = []
		for y in x:
			if y < xi:
				if len(tmp) >= k:
					tmp.sort()
					for j in range(len(tmp) - k + 1):
						c.append(tmp[j])
				tmp = []
			else:
				tmp.append(y)
		if len(tmp) >= k:
			tmp.sort()
			for j in range(len(tmp) - k + 1):
				c.append(tmp[j])
		if len(c) >= q:
			c.sort()
			ret = min(ret, c[q - 1] - xi)
	return ret
(n, k, q) = list(map(int, input().split()))
x = list(map(int, input().split()))
print(main(n, k, q, x))


(n, k, q) = map(int, input().split())
a = list(map(int, input().split()))
ans = 10000000000000
for m in a:
	res = []
	l = []
	for x in a:
		if x < m and l:
			if len(l) >= k:
				l.sort()
				for p in l[:len(l) - k + 1]:
					res.append(p)
			l = []
		elif x >= m:
			l.append(x)
	if l:
		if len(l) >= k:
			l.sort()
			for p in l[:len(l) - k + 1]:
				res.append(p)
	res.sort()
	if len(res) >= q:
		ans = min(ans, res[q - 1] - m)
if ans == 10000000000000:
	print(-1)
else:
	print(ans)


(n, k, q) = list(map(int, input().split()))
A = list(map(int, input().split()))
ans = 10 ** 18
for x in A:
	B = []
	C = []
	for a in A:
		if a >= x:
			C.append(a)
		else:
			if len(C) >= k:
				C.sort()
				B += C[0:len(C) - k + 1]
			C = []
	if len(C) >= k:
		C.sort()
		B += C[0:len(C) - k + 1]
	if len(B) >= q:
		B.sort()
		ans = min(ans, B[q - 1] - x)
print(ans)


import sys
input = sys.stdin.readline
import heapq as hp
(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
Xs = sorted(list(set(A)))
ans = 10 ** 14
for x in Xs:
	Ps = []
	tmp = []
	for a in A:
		if a >= x:
			tmp.append(a)
		else:
			if len(tmp) >= K:
				Ps.append(tmp)
			tmp = []
	if len(tmp) >= K:
		Ps.append(tmp)
	q = []
	for P in Ps:
		P.sort()
		for (i, p) in enumerate(P):
			q.append(p)
			if len(P) - K - i == 0:
				break
	if len(q) < Q:
		break
	q.sort()
	ans = min(ans, q[Q - 1] - x)
print(ans)


(N, K, Q) = map(int, input().split())
alist = list(map(int, input().split()))

def div_by_a(border, dlist):
	divided_list = []
	div = []
	for d in dlist:
		if d < border:
			if len(div) > 0:
				div.sort()
				divided_list.append(div)
				div = []
		else:
			div.append(d)
	else:
		if len(div) > 0:
			div.sort()
			divided_list.append(div)
	return divided_list
answer = 10 ** 9
for a in alist:
	divlist = div_by_a(a, alist)
	cand_list = []
	for div in divlist:
		cand_num = max(0, len(div) - K + 1)
		cand_list.extend(div[:cand_num])
	cand_list.sort()
	if len(cand_list) >= Q:
		answer = min(answer, cand_list[Q - 1] - a)
print(answer)


(n, k, q) = map(int, input().split())
a = list(map(int, input().split()))
num_set = set(a)

def parse(b):
	ret = []
	tmp = []
	for ai in a:
		if ai >= b:
			tmp.append(ai)
		else:
			if len(tmp) >= k:
				tmp.sort(reverse=True)
				for i in range(k - 1, len(tmp)):
					ret.append(tmp[i])
			tmp = []
	else:
		if len(tmp) >= k:
			tmp.sort(reverse=True)
			for i in range(k - 1, len(tmp)):
				ret.append(tmp[i])
			tmp = []
	return ret
ans = 10 ** 10
for b in num_set:
	lis = parse(b)
	if len(lis) < q:
		continue
	ans_tmp = sorted(lis)[q - 1] - min(lis)
	ans = min(ans, ans_tmp)
print(ans)


(N, K, Q) = list(map(int, input().split()))
A = list(map(int, input().split()))
Ac = [(a, i) for (i, a) in enumerate(A)]
Ac.sort()
ans = Ac[Q - 1][0] - Ac[0][0]
imps = [N]
for j in range(N):
	(a, i) = Ac[j]
	imps.append(i)
	imps.sort()
	kp = 0
	possibles = []
	for k in imps:
		if k - kp >= K:
			Ak = A[kp:k]
			Ak.sort()
			possibles += Ak[:len(Ak) - K + 1]
		kp = k + 1
	if len(possibles) < Q:
		break
	possibles.sort()
	ans = min(ans, possibles[Q - 1] - possibles[0])
print(ans)


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
	(n, k, q) = LI()
	a = LI()
	b = [[a[i], i] for i in range(n)]
	b.sort()
	ans = b[q - 1][0] - b[0][0]
	l = [-1, n]
	for i in range(1, n):
		l.append(b[i - 1][1])
		l.sort()
		if b[i - 1][0] == b[i][0]:
			continue
		s = [a[l[i] + 1:l[i + 1]] for i in range(i + 1)]
		c = []
		for si in s:
			si.sort()
			for j in range(len(si) - k + 1):
				c.append(si[j])
		if len(c) < q:
			continue
		c.sort()
		m = c[q - 1] - c[0]
		if m < ans:
			ans = m
	print(ans)
	return

def __starting_point():
	solve()
__starting_point()


(N, K, Q) = map(int, input().split())
(*A,) = map(int, input().split())
ans = 10 ** 18
for i in range(N):
	pv = A[i]
	res = []
	tmp = []
	for a in A:
		if pv <= a:
			tmp.append(a)
		else:
			if len(tmp) >= K:
				tmp.sort()
				res.extend(tmp[:len(tmp) - K + 1])
			tmp = []
	if len(tmp) >= K:
		tmp.sort()
		res.extend(tmp[:len(tmp) - K + 1])
	if Q <= len(res):
		res.sort()
		ans = min(ans, res[Q - 1] - res[0])
print(ans)


(N, K, Q) = list(map(int, input().split()))
A = list(map(int, input().split()))

def calc(x):
	grp = [[]]
	for a in A:
		if a < x and len(grp[-1]) > 0:
			grp.append([])
		if a >= x:
			grp[-1].append(a)
	L = []
	for g in grp:
		g.sort()
		L += g[:max(0, len(g) - K + 1)]
	L.sort()
	if len(L) < Q or L[0] != x:
		return 10 ** 18
	return L[Q - 1] - x
ans = 10 ** 18
for a in A:
	ans = min(ans, calc(a))
print(ans)


import heapq

def main():
	(n, k, q) = map(int, input().split())
	a = tuple(map(int, input().split()))
	m = float('inf')
	for y in sorted(set(a)):
		x = find_x(a, y, k, q)
		if x is None:
			break
		m = min(m, x - y)
	print(m)

def find_x(a, y, k, q):
	gs = groups(a, y, k)
	xs = []
	for g in gs:
		xs.extend(heapq.nsmallest(len(g) - k + 1, g))
	xss = heapq.nsmallest(q, xs)
	if len(xss) < q:
		return None
	return xss[-1]

def groups(a, m, k):
	g = []
	pos = 0
	while pos < len(a):
		i = pos
		while i < len(a) and a[i] < m:
			i += 1
		j = i
		while j < len(a) and a[j] >= m:
			j += 1
		if j - i >= k:
			g.append(a[i:j])
		pos = j
	return g
main()


(N, K, Q) = map(int, input().split())
a = list(map(int, input().split()))
d = [a]
a = sorted(a)
ans = a[Q - 1] - a[0]
while True:
	d_temp = list()
	sub_temp = list()
	for sub in d:
		for c in sub:
			if c != a[0]:
				sub_temp.append(c)
			else:
				d_temp.append(sub_temp)
				sub_temp = list()
		d_temp.append(sub_temp)
		sub_temp = list()
	d = list()
	a = list()
	for sub in d_temp:
		if len(sub) < K:
			continue
		else:
			d.append(sub)
			sub = sorted(sub)
			a.extend(sub[0:len(sub) - K + 1])
	a.sort()
	if len(a) < Q:
		break
	else:
		ans = min(ans, a[Q - 1] - a[0])
print(ans)


(N, K, Q) = map(int, input().split())
A = [int(i) for i in input().split()]
ans = float('inf')
for i in range(N):
	l = A[i]
	A_str = ' '.join([str(a) if a >= l else 'x' for a in A])
	S = [list(map(int, a.split())) for a in A_str.split('x')]
	C = []
	for s in S:
		if len(s) >= K:
			s.sort()
			for i in range(len(s) - K + 1):
				C.append(s[i])
	C.sort()
	if len(C) >= Q:
		ans = min(ans, C[Q - 1] - C[0])
print(ans)


import bisect
(n, k, q) = map(int, input().split())
a = list(map(int, input().split()))
if q == 1:
	print(0)
	return ()
ls = [-1, n]
b = sorted(((a[i], i) for i in range(n)))
ansls = [b[q - 1][0] - b[0][0]]
space = [n]
qc = q
for (i, x) in enumerate(b):
	for j in range(i, n):
		idx = bisect.bisect_left(ls, b[j][1])
		if space[idx - 1] < k:
			continue
		qc -= 1
		space[idx - 1] -= 1
		if qc == 0:
			ansls.append(b[j][0] - x[0])
			break
	ins = bisect.bisect_left(ls, x[1])
	ls.insert(ins, x[1])
	space = []
	qc = q
	for j in range(1, i + 3):
		space.append(ls[j] - ls[j - 1] - 1)
print(min(ansls))


(n, k, q, *a) = map(int, open(0).read().split())
ans = 10 ** 18
for y in set(a):
	c = []
	tmp = []
	for aa in a:
		if aa >= y:
			tmp.append(aa)
		else:
			if len(tmp) >= k:
				c += sorted(tmp)[:len(tmp) - k + 1]
			tmp = []
	if len(tmp) >= k:
		c += sorted(tmp)[:len(tmp) - k + 1]
	if len(c) >= q:
		c.sort()
		x = c[q - 1]
		ans = min(ans, x - y)
print(ans)


(N, K, Q) = a = map(int, input().split())
a = list(map(int, input().split()))
inf = 10 ** 10
ans = inf
for i in range(N):
	small = a[i]
	seq = []
	seqq = []
	for j in range(N):
		if a[j] < small:
			seq.append(seqq)
			seqq = []
		else:
			seqq.append(a[j])
	seq.append(seqq)
	aaa = []
	for s in seq:
		if len(s) >= K:
			s.sort()
			aaa += s[:len(s) - K + 1]
	if len(aaa) >= Q:
		aaa.sort()
		ans = min(ans, aaa[Q - 1] - aaa[0])
print(ans)


def add_list(buf, new_lists, removals):
	l = len(buf)
	if l >= k:
		sbf = sorted(buf)
		removals.extend(sbf[:l - k + 1])
		new_lists.append(buf)
(n, k, q) = map(int, input().split())
aaa = list(map(int, input().split()))
srt = sorted(aaa)
lists = [aaa]
ans = float('inf')
for a in srt:
	new_lists = []
	removals = []
	for lst in lists:
		buf = []
		for b in lst:
			if a > b:
				add_list(buf, new_lists, removals)
				buf = []
			else:
				buf.append(b)
		add_list(buf, new_lists, removals)
	if len(removals) < q:
		break
	removals.sort()
	ans = min(ans, removals[q - 1] - a)
print(ans)


(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
A_sorted = sorted(A)
ans = 10 ** 10
for m in A_sorted:
	lists = []
	tmp = []
	for a in A:
		if a < m:
			lists.append(tmp)
			tmp = []
		else:
			tmp.append(a)
	lists.append(tmp)
	res = []
	for l in lists:
		length = len(l)
		if length < K:
			continue
		l.sort()
		res += l[:length - K + 1]
	res.sort()
	if len(res) >= Q:
		ans = min(ans, res[Q - 1] - m)
print(ans)


printn = lambda x: print(x, end='')
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
ins = lambda : input().strip()
DBG = True and False
BIG = 10 ** 18
R = 10 ** 9 + 7

def ddprint(x):
	if DBG:
		print(x)
import heapq
(n, k, q) = inm()
a = inl()
mn = BIG
for i in range(n):
	lo = a[i]
	gr = []
	bg = -1
	for j in range(n):
		if lo <= a[j]:
			if bg < 0:
				bg = j
		elif bg >= 0:
			if j >= bg + k:
				gr.append((bg, j))
			bg = -1
	if bg >= 0 and n >= bg + k:
		gr.append((bg, n))
	ddprint(gr)
	h = []
	for (bg, ed) in gr:
		b = a[bg:ed]
		b.sort()
		for j in range(len(b) - k + 1):
			heapq.heappush(h, b[j])
	ddprint(h)
	if len(h) < q:
		continue
	mn0 = BIG
	mx = -1
	for j in range(q):
		v = heapq.heappop(h)
		mx = max(mx, v)
		mn0 = min(mn0, v)
	mn = min(mn, mx - mn0)
print(mn)


import sys
input = sys.stdin.readline
(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
ans = float('inf')
for lb in sorted(A):
	tmp = []
	use = []
	for a in A + [-1]:
		if a >= lb:
			tmp.append(a)
		else:
			if len(tmp) >= K:
				use += sorted(tmp)[:len(tmp) - K + 1]
			tmp = []
	if len(use) < Q:
		break
	ans = min(ans, sorted(use)[Q - 1] - lb)
print(ans)


(n, k, q) = map(int, input().split())
a = list(map(int, input().split()))
set_a = sorted(set(a))
result = 1000000000
for y in set_a:
	counter = 0
	candidate = []
	for i in range(n):
		if a[i] < y:
			if counter >= k:
				candidate = candidate + sorted(a[i - counter:i])[:counter - k + 1]
			counter = 0
		elif i == n - 1:
			if counter + 1 >= k:
				candidate = candidate + sorted(a[i - counter:i + 1])[:counter - k + 2]
		else:
			counter += 1
	if len(candidate) >= q:
		z = sorted(candidate)[q - 1] - y
		if z < result:
			result = z
print(result)


(n, k, q) = [int(item) for item in input().split()]
a = [int(item) for item in input().split()] + [-1]
ans = 10 ** 15
for min_val in a[:-1]:
	takeble = []
	(l, r) = (-1, -1)
	for (i, item) in enumerate(a):
		if item >= min_val and l == -1:
			l = i
		elif item < min_val and l != -1:
			r = i
			takeble.append(a[l:r])
			l = -1
	taken = []
	for part in takeble:
		if len(part) < k:
			continue
		part.sort()
		taken += part[:len(part) - k + 1]
	if len(taken) < q:
		continue
	taken.sort()
	ans = min(ans, taken[q - 1] - taken[0])
print(ans)


inf = float('inf')

def calc_max_a(min_a):
	cands = []
	seq = 0
	for (i, aa) in enumerate(a):
		if aa < min_a:
			if seq >= K:
				cands.extend(sorted(a[i - seq:i])[:seq - K + 1])
			seq = 0
		else:
			seq += 1
	if seq >= K:
		cands.extend(sorted(a[-seq:])[:seq - K + 1])
	if len(cands) < Q:
		return -1
	else:
		return sorted(cands)[Q - 1]
(N, K, Q) = map(int, input().split())
a = tuple(map(int, input().split()))
ans = inf
for min_a in sorted(set(a)):
	max_a = calc_max_a(min_a)
	if max_a < 0:
		break
	ans = min(ans, max_a - min_a)
print(ans)


import sys
input = sys.stdin.readline
import heapq as hp

def main():
	(N, K, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	NUM = sorted(list(set(A)))
	ans = 10 ** 10
	for n in NUM:
		Qs = []
		q = []
		for i in range(N):
			if A[i] < n:
				if q:
					Qs.append(q)
					q = []
				continue
			if not q:
				q = [A[i]]
			else:
				hp.heappush(q, A[i])
		if q:
			Qs.append(q)
		P = []
		for q in Qs:
			l = len(q)
			if l < K:
				continue
			for _ in range(min(Q, l - K + 1)):
				v = hp.heappop(q)
				P.append(v)
		if len(P) < Q:
			break
		P.sort()
		ans = min(ans, P[Q - 1] - P[0])
	print(ans)

def __starting_point():
	main()
__starting_point()


(N, K, Q) = map(int, input().split())
X = list(map(int, input().split()))
r = 10 ** 18
for y in X:
	tmp = []
	tmp2 = []
	for x in X:
		if x < y:
			tmp.sort()
			tn = len(tmp)
			if len(tmp) > K - 1:
				tmp2 += tmp[:tn - K + 1]
			tmp = []
			continue
		tmp.append(x)
	tmp.sort()
	tn = len(tmp)
	if tn - K + 1 > 0:
		tmp2 += tmp[:tn - K + 1]
	tmp2.sort()
	if len(tmp2) >= Q:
		r = min(r, tmp2[Q - 1] - y)
print(r)


from heapq import heappush, heappop
(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
ans = float('inf')
for x in A:
	data = []
	h = []
	for i in range(N):
		if A[i] >= x:
			heappush(h, A[i])
		elif h:
			data.append(h)
			h = []
	if h:
		data.append(h)
	lsls = []
	for h in data:
		for j in range(max(0, len(h) - K + 1)):
			lsls.append(heappop(h))
	lsls.sort()
	if len(lsls) >= Q:
		ans = min(ans, lsls[Q - 1] - lsls[0])
print(ans)


(N, K, Q) = list(map(int, input().split()))
A = [int(i) for i in input().split()]

def solve():
	if Q == 1:
		return 0
	ret = float('inf')
	for i in range(N):
		l = -1
		for j in range(i, max(-1, i - K), -1):
			if A[j] < A[i]:
				l = j
				break
		r = N
		for j in range(i, min(N, i + K)):
			if A[j] < A[i]:
				r = j
				break
		if r - l - 1 < K:
			continue
		B = A[:]
		B.pop(i)
		C = [-1]
		for j in range(N - 1):
			if B[j] < A[i]:
				C.append(j)
		C.append(N - 1)
		D = []
		for j in range(len(C) - 1):
			if C[j + 1] - C[j] >= K:
				D += sorted(B[C[j] + 1:C[j + 1]])[:C[j + 1] - C[j] - K]
		if len(D) >= Q - 1:
			D.sort()
			ret = min(ret, D[Q - 2] - A[i])
	return ret
print(solve())


import sys
input = sys.stdin.readline
(N, K, Q) = map(int, input().split())
a = list(map(int, input().split()))
tt = a[:]
inf = 10 ** 10
res = inf + 0
for mn in sorted(set(a)):
	t = [[]]
	for i in range(N):
		if tt[i] == inf:
			if t[-1] != []:
				t.append([])
		else:
			t[-1].append(a[i])
	ttt = []
	for i in range(len(t)):
		t[i].sort()
		for j in range(len(t[i]) - K + 1):
			ttt.append(t[i][j])
	if len(ttt) < Q:
		break
	ttt.sort()
	res = min(res, ttt[Q - 1] - ttt[0])
	for i in range(N):
		if a[i] == mn:
			tt[i] = inf
print(res)


(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
sortedA = sorted(set(A))
ans = []
for v in sortedA:
	C = [[]]
	for (i, t) in enumerate(A):
		if t < v and len(C[-1]) > 0:
			C.append([])
		if t >= v:
			C[-1].append(t)
	tmp = []
	for t in C:
		if len(t) >= K:
			tmp += sorted(t)[:len(t) - K + 1]
	tmp.sort()
	if len(tmp) >= Q:
		ans.append(tmp[Q - 1] - v)
print(min(ans))


(N, K, Q) = map(int, input().split())
A = [int(i) for i in input().split()]
A += [0]
S = sorted(A)
ans = []
for i in range(1, N + 1):
	if S[i] == S[i - 1]:
		continue
	mi = S[i]
	L = []
	x = 0
	for y in range(N + 1):
		if A[y] < mi:
			if y - x >= K:
				L += sorted(A[x:y])[:y - x - K + 1]
			x = y + 1
	if len(L) < Q:
		continue
	L.sort()
	ans.append(L[Q - 1] - mi)
print(min(ans))


import sys
readline = sys.stdin.readline
read = sys.stdin.read
(n, k, Q) = map(int, readline().split())
(*a,) = map(int, readline().split())
(*sa,) = sorted(a)
a.append(-1)
ans = 10 ** 9
for i in sa:
	q = []
	v = []
	for j in a:
		if j < i:
			if len(v) >= k:
				v.sort()
				q += v[:len(v) - k + 1]
			v.clear()
		else:
			v.append(j)
	if len(q) < Q:
		break
	q.sort()
	ans = min(ans, q[Q - 1] - q[0])
print(ans)


(N, K, Q) = map(int, input().split())
A = [int(i) for i in input().split()]

def main():
	ans = float('inf')
	for i in range(N):
		can = []
		left = 0
		while left < N:
			right = left
			while right < N and A[i] <= A[right]:
				right += 1
			L = right - left
			tmp = sorted([A[j] for j in range(left, right)])
			can += tmp[:max(0, L - K + 1)]
			left = right + 1
		can.sort()
		if len(can) >= Q:
			ans = min(ans, can[Q - 1] - A[i])
	print(ans)
main()


(N, K, Q) = map(int, input().split())
A = [int(a) for a in input().split()]
S = set(A)
I = sorted(list(S))
m = len(I)
D = {a: i for (i, a) in enumerate(I)}
ans = 1 << 30
for i in range(m):
	l = I[i]
	LL = []
	L = []
	for a in A:
		if a < l:
			if L:
				if len(L) >= K:
					LL += sorted(L)[:len(L) - K + 1]
				L = []
		else:
			L.append(a)
	if L:
		if len(L) >= K:
			LL += sorted(L)[:len(L) - K + 1]
	if len(LL) >= Q:
		ans = min(ans, sorted(LL)[Q - 1] - l)
print(ans)


(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))

def list_split(arr, x):
	ret = []
	d = []
	for v in arr:
		if v >= x:
			d.append(v)
		elif d:
			ret.append(d)
			d = []
	else:
		if d:
			ret.append(d)
	return ret
ans = 10 ** 9
for x in sorted(A):
	y = []
	for arr in list_split(A, x):
		la = len(arr)
		if la >= K:
			y += sorted(arr)[:min(la - K + 1, Q)]
	if len(y) >= Q:
		ans = min(ans, sorted(y)[Q - 1] - x)
print(ans)


(n, k, q) = map(int, input().split())
a = [int(x) for x in input().split()]
m = None
for x in a:
	b = []
	c = []
	for y in a:
		if y < x:
			if len(c) >= k:
				c.sort()
				b.extend(c[:len(c) - k + 1])
			c = []
		else:
			c.append(y)
	if len(c) >= k:
		c.sort()
		b.extend(c[:len(c) - k + 1])
	if len(b) >= q:
		b.sort()
		if m is None or m > b[q - 1] - x:
			m = b[q - 1] - x
print(m)


from itertools import groupby, chain
(N, K, Q, *A) = map(int, open(0).read().split())
ans = float('inf')
for Y in set(A):
	C = sorted(chain.from_iterable((v[:len(v) - K + 1] for v in (sorted(v) for (k, v) in groupby(A, key=lambda a: a >= Y) if k) if len(v) >= K)))
	if len(C) >= Q:
		ans = min(ans, C[Q - 1] - Y)
print(ans)


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
(N, K, Q) = MAP()
A = LIST()
ans = INF
for x in A:
	B = []
	tmp = []
	for i in range(N):
		if A[i] >= x:
			tmp.append(A[i])
		else:
			B.append(tmp)
			tmp = []
	B.append(tmp)
	C = []
	for li in B:
		m = len(li)
		li.sort()
		C += li[:max(m - K + 1, 0)]
	C.sort()
	if len(C) < Q:
		continue
	y = C[Q - 1]
	ans = min(ans, y - x)
print(ans)


(n, k, q) = map(int, input().split())
a = list(map(int, input().split()))
result = 100000000000
for j in range(n):
	li = [[]]
	for i in range(n):
		if a[j] <= a[i]:
			li[-1].append(a[i])
		else:
			li.append([])
	ans = []
	for li_ele in li:
		if len(li_ele) < k:
			continue
		else:
			tmp = sorted(li_ele)
			ans = ans + tmp[0:len(li_ele) - k + 1]
	ans = sorted(ans)
	if len(ans) >= q:
		result = min(ans[q - 1] - a[j], result)
print(result)


from collections import defaultdict
from bisect import bisect_left
(n, k, q) = map(int, input().split())
a = list(map(int, input().split()))
s = sorted(list(set(a)))
dic = defaultdict(list)
for (i, j) in enumerate(a):
	dic[j].append(i)
ans = 10 ** 20
use = [-1, n]
for i in range(len(s)):
	l = []
	for j in range(len(use) - 1):
		(x, y) = (use[j], use[j + 1])
		if y - x - 1 >= k:
			l2 = []
			for t in range(x + 1, y):
				l2.append(a[t])
			l2.sort()
			for t in range(y - x - k):
				l.append(l2[t])
	if len(l) >= q:
		l.sort()
		ans = min(ans, l[q - 1] - l[0])
	for j in dic[s[i]]:
		use.insert(bisect_left(use, j), j)
print(ans)


from heapq import nsmallest

def get_add_list():
	cache = {}

	def add_list(s, t):
		global new_lists, removables
		l = t - s
		if l >= k:
			new_lists.append((s, t))
			if (s, t) in cache:
				removables.extend(cache[s, t])
				return
			cache[s, t] = nsmallest(l - k + 1, aaa[s:t])
			removables.extend(cache[s, t])
	return add_list
(n, k, q) = map(int, input().split())
aaa = list(map(int, input().split()))
srt = sorted(set(aaa))
lists = [(0, n)]
ans = float('inf')
add_list = get_add_list()
for a in srt:
	new_lists = []
	removables = []
	for (s, t) in lists:
		r = s
		for (i, b) in enumerate(aaa[s:t]):
			if a > b:
				add_list(r, s + i)
				r = s + i + 1
		add_list(r, t)
	if len(removables) < q:
		break
	removables.sort()
	ans = min(ans, removables[q - 1] - a)
	lists = new_lists
print(ans)


(n, k, q) = map(int, input().split())
arr = list(map(int, input().split()))
ans = 10 ** 18
for val in arr:
	tmp = []
	vals = []
	for i in range(n):
		if arr[i] >= val:
			tmp.append(arr[i])
		else:
			if len(tmp) >= k:
				tmp = sorted(tmp)
				vals.extend(tmp[:len(tmp) - k + 1])
			tmp = []
	if len(tmp) >= k:
		tmp = sorted(tmp)
		vals.extend(tmp[:len(tmp) - k + 1])
	if len(vals) < q:
		continue
	else:
		vals = sorted(vals)
		ans = min(ans, vals[q - 1] - vals[0])
print(ans)


(n, k, q) = map(int, input().split())
a = list(map(int, input().split()))
d = [a]
a = sorted(a)
ans = a[q - 1] - a[0]
while True:
	newd = list()
	li = list()
	for sub in d:
		for c in sub:
			if c != a[0]:
				li.append(c)
			else:
				newd.append(li)
				li = list()
		newd.append(li)
		li = list()
	d = list()
	a = list()
	for li in newd:
		if len(li) < k:
			continue
		else:
			d.append(li)
			li = sorted(li)
			a.extend(li[0:len(li) - k + 1])
	a.sort()
	if len(a) >= q:
		ans = min(a[q - 1] - a[0], ans)
	else:
		break
print(ans)


(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))

def sol(y):
	B = [[]]
	for a in A:
		if a < y and len(B[-1]) > 0:
			B.append([])
		if a >= y:
			B[-1].append(a)
	C = []
	for grp in B:
		grp.sort()
		C += grp[:max(0, len(grp) - K + 1)]
	C.sort()
	return C[Q - 1] - y if len(C) >= Q and C[0] == y else 10 ** 18
ans = 10 ** 18
for y in A:
	ans = min(ans, sol(y))
print(ans)


import sys

def MI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))
(N, K, Q) = MI()
A = LI()
ans = 10 ** 18
for i in range(N):
	a = A[i]
	(left, right) = (0, 0)
	X = []
	while right < N:
		if A[right] >= a:
			right += 1
		else:
			if right - left >= K:
				Y = A[left:right]
				Y.sort()
				for j in range(right - left - K + 1):
					X.append(Y[j])
			right += 1
			left = right
	if right - left >= K:
		Y = A[left:right]
		Y.sort()
		for j in range(right - left - K + 1):
			X.append(Y[j])
	if len(X) < Q or min(X) != a:
		continue
	X.sort()
	ans = min(ans, X[Q - 1] - a)
print(ans)


(n, k, q, *a) = map(int, open(0).read().split())
s = sorted
m = 1000000000.0
for b in a:
	i = [i for (i, t) in enumerate(a) if t < b]
	l = s(sum([s(a[i + 1:j])[::-1][k - 1:] for (i, j) in zip([-1] + i, i + [n])], []))[q - 1:]
	if l:
		m = min(m, l[0] - b)
print(m)


import sys
input = sys.stdin.readline
(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
cannot_use = set([-1])
ans = float('inf')
for i in sorted(A):
	tmp = []
	use = []
	for a in A + [-1]:
		if a not in cannot_use:
			tmp.append(a)
		else:
			if len(tmp) >= K:
				tmp.sort()
				use += tmp[:len(tmp) - K + 1]
			tmp = []
	use.sort()
	if len(use) < Q:
		break
	ans = min(ans, use[Q - 1] - i)
	cannot_use.add(i)
print(ans)


(N, K, Q) = map(int, input().split())
A = [int(a) for a in input().split()]
minSub = 10 ** 10
for a in A:
	start = False
	end = 0
	(subarray, newarray) = ([], [])
	for i in range(N):
		if A[i] >= a:
			newarray.append(A[i])
			start = True
		elif start:
			start = False
			if len(newarray) >= K:
				newarray.sort()
				for j in range(len(newarray) - K + 1):
					subarray.append(newarray[j])
			newarray = []
	if len(newarray) >= K:
		newarray.sort()
		for j in range(len(newarray) - K + 1):
			subarray.append(newarray[j])
	if len(subarray) >= Q:
		subarray.sort()
		minSub = min(minSub, subarray[Q - 1] - a)
print(minSub)


import sys, heapq

def input():
	return sys.stdin.readline()[:-1]
(n, k, q) = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)
a = [0] + a + [0]
ans = 10 ** 30
for x in b:
	removed = []
	que = []
	for i in range(n + 2):
		if a[i] < x:
			que = []
		else:
			heapq.heappush(que, a[i])
			if len(que) == k:
				removed.append(heapq.heappop(que))
	if len(removed) < q:
		continue
	removed.sort()
	ans = min(ans, removed[q - 1] - x)
print(ans)


(n, k, q) = map(int, input().split())
if q == 1:
	print(0)
	return ()
(*a,) = map(int, input().split())
a += [-1]
ans = 10 ** 10
for i in range(n):
	ai = a[i]
	tmp = [10 ** 11]
	tmp2 = [ai]
	for j in range(n + 1):
		if i == j:
			continue
		if a[j] < ai:
			tmp.sort()
			if len(tmp) >= k + 1:
				tmp2 += tmp[:-k]
			tmp = [10 ** 11]
		else:
			tmp.append(a[j])
	tmp2.sort()
	if len(tmp2) >= q:
		ans = min(ans, tmp2[q - 1] - ai)
print(ans)


(n, k, q) = map(int, input().split())
l = list(map(int, input().split()))
ans = 10 ** 10
for i in range(n):
	x = l[i]
	tmp = []
	z = []
	for j in range(n):
		if l[j] >= x:
			tmp.append(l[j])
		if l[j] < x or j == n - 1:
			tmp.sort()
			if len(tmp) - k + 1 > 0:
				z += tmp[:len(tmp) - k + 1]
			tmp = []
	z.sort()
	if len(z) >= q:
		ans = min(ans, z[q - 1] - x)
print(ans)


import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7

def argsort(li, key=None, reverse=False):
	return [i for (_, i) in sorted([(a, i) for (i, a) in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse)]
(N, K, Q) = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))

def count(l, r, M):
	ret = 0
	for i in range(l, r):
		ret += A[i] <= M
	return min(r - l - K + 1, ret)

def test(M, lr):
	cnt = 0
	for (l, r) in lr:
		cnt += count(l, r, M)
		if cnt >= Q:
			return True
	return False

def split(lr, i):
	ret = []
	for (l, r) in lr:
		if l <= i < r:
			if i - l >= K:
				ret.append((l, i))
			if r - (i + 1) >= K:
				ret.append((i + 1, r))
		else:
			ret.append((l, r))
	return ret
lr = [(0, N)]
ans = max(A) - min(A)
idx = argsort(A)
for i in idx:
	m = A[i]
	if test(m + ans - 1, lr):
		ok = m + ans - 1
		ng = m - 1
		while abs(ok - ng) > 1:
			mid = (ok + ng) // 2
			if test(mid, lr):
				ok = mid
			else:
				ng = mid
		ans = ok - m
	lr = split(lr, i)
	if not lr:
		break
print(ans)


(n, k, q) = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = 10 ** 9
for i in a:
	A = []
	l = []
	ln = 0
	for j in a + [-1]:
		if i > j:
			if ln - k + 1 >= 0:
				l.sort()
				A += l[:ln - k + 1]
			l = []
			ln = 0
		else:
			l.append(j)
			ln += 1
	if len(A) < q:
		continue
	else:
		A.sort()
		ans = min(ans, A[q - 1] - i)
print(ans)


(n, k, q, *a) = map(int, open(0).read().split())
s = sorted
m = 1e+18
for b in a:
	i = [i for (i, t) in enumerate(a) if t < b]
	l = s((u for t in [s(a[i + 1:j])[::-1][k - 1:] for (i, j) in zip([-1] + i, i + [n])] for u in t))
	if len(l) >= q:
		m = min(m, l[q - 1] - b)
print(m)


def main():

	def calc_x_y(mi):
		cont = 0
		removed = []
		for (i, x) in enumerate(a):
			if x < mi:
				if cont >= K:
					removed += sorted(a[i - cont:i])[:cont - K + 1]
				cont = 0
				continue
			cont += 1
		else:
			if cont >= K:
				removed += sorted(a[-cont:])[:cont - K + 1]
		if len(removed) >= Q:
			removed.sort()
			return removed[Q - 1] - mi
		else:
			return -1
	(N, K, Q) = list(map(int, input().split()))
	(*a,) = list(map(int, input().split()))
	mi_cands = sorted(set(a))
	ans = 10 ** 9
	for mi in mi_cands:
		res = calc_x_y(mi)
		if ~res:
			ans = min(ans, res)
	print(ans)

def __starting_point():
	main()
__starting_point()


(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
ans = float('inf')
for X in A:
	S = ' '.join([str(a) if a >= X else 'x' for a in A])
	S = [list(map(int, Sx.split())) for Sx in S.split('x')]
	C = []
	for s in S:
		s.sort(reverse=True)
		if len(s) >= K:
			for ss in s[K - 1:]:
				C.append(ss)
	C.sort()
	if len(C) >= Q:
		ans = min(ans, C[Q - 1] - X)
print(ans)


(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
a = list(set(A))
a.sort()
ans = float('inf')

def condition(i, num):
	if i > a[num]:
		return False
	X = a[num]
	Y = A[i]
	check = 0
	stack = 0
	count = 0
	for k in range(0, N):
		if A[k] > X:
			stack += 1
		elif A[k] >= Y:
			stack += 1
			count += 1
		else:
			t = stack + 1 - K
			check += max(min(t, count), 0)
			stack = 0
			count = 0
	t = stack + 1 - K
	check += max(min(t, count), 0)
	return check >= Q
for i in range(0, N):
	start = 0
	end = len(a) - 1
	while end - start > 1:
		test = (end + start) // 2
		if condition(i, test):
			end = test
		else:
			start = test
	if condition(i, start):
		ans = min(ans, a[start] - A[i])
	elif condition(i, end):
		ans = min(ans, a[end] - A[i])
print(ans)


(n, k, q) = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
ans = 10 ** 9
for i in a:
	(p, s, f) = ([], 0, 1)
	for j in range(n):
		if a[j] >= i and f:
			(s, f) = (j, 0)
		elif a[j] < i and f - 1:
			if j - s >= k:
				for j2 in sorted(a[s:j])[:j - s - k + 1]:
					p.append(j2)
			f = 1
	if f - 1 and n - s >= k:
		for j2 in sorted(a[s:n])[:n - s - k + 1]:
			p.append(j2)
	if len(p) >= q:
		ans = min(ans, sorted(p)[q - 1] - i)
print(ans)


(n, k, q) = map(int, input().split())
a = list(map(int, input().split()))
ans = 10 ** 10
for y in a:
	t = [[]]
	for i in a:
		if i < y:
			if len(t[-1]):
				t.append([])
		else:
			t[-1].append(i)
	if len(t[-1]) == 0:
		del t[-1]
	m = []
	for i in t:
		if len(i) < k:
			continue
		m += sorted(i)[:len(i) - k + 1]
	if len(m) < q:
		continue
	m.sort()
	ans = min(ans, m[q - 1] - y)
print(ans)


(n, k, q) = list(map(int, input().split()))
a = list(map(int, input().split()))
if q == 1:
	print(0)
	return ()
ans = 10 ** 10
for (i, y) in enumerate(a):
	li = []
	l = 0
	cnd = []
	for (j, x) in enumerate(a + [-1]):
		if i == j:
			continue
		if x < y:
			if l - k + 1 >= 0:
				li.sort()
				cnd += li[:l - k + 1]
			li = []
			l = 0
		else:
			li.append(x)
			l += 1
	if len(cnd) >= q - 1:
		cnd.sort()
		sub = cnd[q - 2] - y
		ans = min(ans, sub)
print(ans)


from heapq import heappop, heappush
(n, k, q) = map(int, input().split())
a = list(map(int, input().split()))
if q == 1:
	print(0)
	exit()
ans = max(a)
rem = [0] * n
while True:
	nums = [[]]
	i = 0
	while i < n:
		if rem[i] == 0:
			heappush(nums[-1], a[i])
		elif nums[-1]:
			nums.append([])
		i += 1
	mins = []
	for hq in nums:
		while len(hq) >= k:
			mins.append(heappop(hq))
	if len(mins) < q:
		print(ans)
		exit()
	mins.sort()
	y = mins[0]
	x = mins[q - 1]
	ans = min(ans, x - y)
	for (i, ai) in enumerate(a):
		if ai == y:
			rem[i] = 1


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
sys.setrecursionlimit(2147483647)
INF = 1 << 100

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007
(n, k, q) = LI()
A = LI()

def list_split(arr, x):
	ret = []
	d = []
	for v in arr:
		if v >= x:
			d += [v]
		elif d:
			ret += [d]
			d = []
	else:
		ret += [d]
	return ret
ans = INF
for e in set(A):
	y = []
	for arr in list_split(A, e):
		l = len(arr)
		if l >= k:
			y += sorted(arr)[:min(l - k + 1, q)]
	if len(y) >= q:
		ans = min(ans, sorted(y)[q - 1] - e)
print(ans)


(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
SA = sorted(A)

def calc_max_a(min_a):
	cands = []
	seq = 0
	for (i, a) in enumerate(A):
		if a < min_a:
			if seq >= K:
				cands += sorted(A[i - seq:i])[:seq - K + 1]
			seq = 0
		else:
			seq += 1
	if seq >= K:
		cands += sorted(A[-seq:])[:seq - K + 1]
	if len(cands) < Q:
		return -1
	else:
		return sorted(cands)[Q - 1]
min_a = 0
ans = float('inf')
for a in SA:
	if a == min_a:
		continue
	min_a = a
	max_a = calc_max_a(min_a)
	if max_a < 0:
		break
	ans = min(ans, max_a - min_a)
print(ans)


inf = 10 ** 9
(n, k, q) = map(int, input().split())
a = tuple(map(int, input().split()))
ans = inf
for min_ in sorted(set(a)):
	res = []
	seq = 0
	for (ind, a_) in enumerate(a):
		if a_ >= min_:
			seq += 1
		else:
			if seq >= k:
				sequence_le_k = a[ind - seq:ind]
				pick = seq - k + 1
				res.extend(sorted(sequence_le_k)[:pick])
			seq = 0
	else:
		if seq >= k:
			sequence_le_k = a[-seq:]
			pick = seq - k + 1
			res.extend(sorted(sequence_le_k)[:pick])
	if len(res) < q:
		continue
	res.sort()
	ans = min(ans, res[q - 1] - min_)
print(ans)


from collections import defaultdict
(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
A_sorted = sorted(A)
ans = float('inf')
ap = 0
for (i, a) in enumerate(A_sorted):
	if a == ap:
		continue
	ap = a
	L = [0]
	d = defaultdict(list)
	for aa in A:
		if aa < a:
			if L[-1] == 0:
				continue
			else:
				L.append(0)
		else:
			L[-1] += 1
			d[aa].append(len(L) - 1)
	cnt = 0
	aap = 0
	for aa in A_sorted[i:]:
		if aap == aa:
			continue
		aap = aa
		for v in d[aa]:
			if L[v] >= K:
				L[v] -= 1
				cnt += 1
		if cnt >= Q:
			break
	else:
		break
	ans = min(ans, aa - a)
print(ans)


import heapq
(N, K, Q) = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
sA = sorted(set(A))
A += [-1]
ans = float('inf')
for amin in sA:
	cand = []
	fr = 0
	to = -1
	for i in range(N + 1):
		a = A[i]
		if a >= amin:
			if fr == -1:
				fr = i
		elif a < amin and fr >= 0:
			cand += sorted(A[fr:i])[:max(0, i - fr - K + 1)]
			fr = -1
	if len(cand) < Q:
		break
	ans = min(ans, sorted(cand)[Q - 1] - amin)
print(ans)


from collections import defaultdict, deque, Counter
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right
import sys

def getN():
	return int(input())

def getNM():
	return map(int, input().split())

def getList():
	return list(map(int, input().split()))

def getArray(intn):
	return [int(input()) for i in range(intn)]

def input():
	return sys.stdin.readline().rstrip()

def rand_N(ran1, ran2):
	return random.randint(ran1, ran2)

def rand_List(ran1, ran2, rantime):
	return [random.randint(ran1, ran2) for i in range(rantime)]

def rand_ints_nodup(ran1, ran2, rantime):
	ns = []
	while len(ns) < rantime:
		n = random.randint(ran1, ran2)
		if not n in ns:
			ns.append(n)
	return sorted(ns)

def rand_query(ran1, ran2, rantime):
	r_query = []
	while len(r_query) < rantime:
		n_q = rand_ints_nodup(ran1, ran2, 2)
		if not n_q in r_query:
			r_query.append(n_q)
	return sorted(r_query)
sys.setrecursionlimit(1000000000)
mod = 998244353
(N, K, Q) = getNM()
A = getList()
A = [[A[i], i] for i in range(N)]
flag = [0] * N
l = deepcopy(sorted(A))
opt = []
l.sort()
for i in range(Q):
	opt.append(l[i][0])
ans = opt[-1] - opt[0]
for i in range(N):
	flag[l[i][1]] = 1
	parent = []
	child = []
	for j in range(N):
		if flag[j] == 0:
			child.append(A[j][0])
		else:
			child.sort()
			parent.append(child)
			child = []
	if len(child):
		child.sort()
		parent.append(child)
	opt = []
	for array in parent:
		for j in range(len(array) - K + 1):
			opt.append(array[j])
	if len(opt) >= Q:
		opt.sort()
		ans = min(ans, opt[Q - 1] - opt[0])
print(ans)


(N, K, Q) = map(int, input().split())
As = list(map(int, input().split()))
ans = 10 ** 9
for Y in sorted(As)[:N - Q - K + 2]:
	cands = []
	cs = []
	for A in As + [0]:
		if A < Y:
			if len(cs) >= K:
				cands += sorted(cs)[:len(cs) - K + 1]
			cs = []
		else:
			cs += [A]
	if len(cands) < Q:
		continue
	X = sorted(cands)[Q - 1]
	ans = min(ans, X - Y)
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]
(n, k, q) = MI()
aa = LI()
pp = list(sorted(set(aa)))

def diff(p):
	can = []
	cur = []
	for a in aa + [-1]:
		if a < p:
			if len(cur) == n:
				can = cur
				break
			if len(cur) >= k:
				cur.sort()
				if k == 1:
					can += cur
				else:
					can += cur[:-(k - 1)]
			cur = []
		else:
			cur.append(a)
	if len(can) < q:
		return -1
	can.sort()
	res = can[q - 1] - can[0]
	return res
ans = 10 ** 16
for p in pp:
	ret = diff(p)
	if ret == -1:
		break
	ans = min(ans, ret)
print(ans)


import sys

def main():
	input = sys.stdin.readline
	(N, K, Q) = map(int, input().split())
	(*A,) = map(int, input().split())
	ans = 10 ** 10
	from heapq import heappop, heappush
	A.append(-1)
	for y in A:
		if y == -1:
			break
		c = []
		t = []
		for a in A:
			if a >= y:
				heappush(t, a)
			else:
				for _ in range(len(t) - (K - 1)):
					heappush(c, heappop(t))
				t = []
		if len(c) < Q:
			continue
		x = [heappop(c) for _ in range(Q)][-1]
		ans = min(ans, x - y)
	print(ans)

def __starting_point():
	main()
__starting_point()


def main():
	(N, K, Q, *A) = map(int, open(0).read().split())
	ans = float('inf')
	for Y in set(A):
		C = []
		tmp = []
		for a in A:
			if a >= Y:
				tmp.append(a)
			else:
				if len(tmp) >= K:
					C += sorted(tmp)[:len(tmp) - K + 1]
				tmp = []
		if len(tmp) >= K:
			C += sorted(tmp)[:len(tmp) - K + 1]
		if len(C) >= Q:
			C.sort()
			X = C[Q - 1]
			ans = min(ans, X - Y)
	print(ans)
main()


(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
ans = 10 ** 10
for a in A:
	candidates = []
	tmp = []
	for b in A:
		if a <= b:
			tmp.append(b)
		else:
			if K > 1:
				for i in sorted(tmp)[:-K + 1]:
					candidates.append(i)
			else:
				for i in sorted(tmp):
					candidates.append(i)
			tmp = []
	if K > 1:
		for i in sorted(tmp)[:-K + 1]:
			candidates.append(i)
	else:
		for i in sorted(tmp):
			candidates.append(i)
	candidates.sort()
	if len(candidates) >= Q:
		ans = min(ans, candidates[Q - 1] - a)
print(ans)


(n, k, q) = map(int, input().split())
a = list(map(int, input().split()))
ans = 10 ** 10
for x in a:
	b = [[]]
	can = 0
	for i in a:
		if i < x:
			if len(b[-1]):
				b.append([])
		else:
			b[-1].append(i)
	if len(b[-1]) == 0:
		del b[-1]
	for i in range(len(b)):
		b[i].sort()
	c = []
	for i in b:
		i.sort()
		if len(i) >= k:
			c += i[:len(i) - k + 1]
	if len(c) < q:
		continue
	c.sort()
	ans = min(ans, c[q - 1] - c[0])
print(ans)


import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10 ** 7)

def input():
	return sys.stdin.readline()[:-1]
mod = 10 ** 9 + 7

def I():
	return int(input())

def LI():
	return list(map(int, input().split()))

def LIR(row, col):
	if row <= 0:
		return [[] for _ in range(col)]
	elif col == 1:
		return [I() for _ in range(row)]
	else:
		read_all = [LI() for _ in range(row)]
		return map(list, zip(*read_all))
(N, K, Q) = LI()
A = LI()
Aval = set(A)
ans = float('inf')
for a in Aval:
	now = []
	mins = []
	num = 0
	for i in range(N):
		if A[i] >= a:
			now.append(A[i])
		else:
			if len(now) >= K:
				now.sort()
				mins.extend(now[:len(now) - K + 1])
				num += len(now) - K + 1
			now = []
	if len(now) >= K:
		now.sort()
		mins.extend(now[:len(now) - K + 1])
		num += len(now) - K + 1
	if num >= Q:
		mins.sort()
		if mins[Q - 1] - a < ans:
			ans = mins[Q - 1] - a
print(ans)


def search(x, K, Q, A):
	cand = []
	i = 0
	while i < len(A):
		tmp = []
		while i < len(A):
			if A[i] >= x:
				tmp.append(A[i])
				i += 1
			else:
				i += 1
				break
		if len(tmp) >= K:
			tmp.sort()
			L = len(tmp) - K + 1
			cand.extend(tmp[:L])
	if len(cand) < Q:
		return -1
	else:
		return sorted(cand)[Q - 1]

def main():
	(N, K, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	if Q == 1:
		return 0
	res = 10 ** 18
	for (i, x) in enumerate(A):
		rest = A[:i] + A[i + 1:]
		y = search(x, K, Q - 1, rest)
		if y == -1:
			continue
		res = min(res, y - x)
	return res
print(main())


import sys
INF = 1 << 60
MOD = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
input = lambda : sys.stdin.readline().rstrip()
from itertools import groupby
from heapq import heappop, heappush, heapify

def resolve():
	(n, k, q) = map(int, input().split())
	A = list(map(int, input().split()))
	ans = INF
	for m in sorted(A):
		C = []
		for (key, it) in groupby(A, key=lambda a: a >= m):
			if key is False:
				continue
			D = list(it)
			if len(D) >= k:
				D.sort()
				C.append(D[:len(D) - k + 1][::-1])
		if sum((len(a) for a in C)) < q:
			continue
		heap = [(C[i].pop(), i) for i in range(len(C))]
		heapify(heap)
		for _ in range(q):
			(M, i) = heappop(heap)
			if C[i]:
				heappush(heap, (C[i].pop(), i))
		ans = min(ans, M - m)
	print(ans)
resolve()


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 15
mod = 10 ** 9 + 7

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	(n, k, q) = LI()
	a = LI() + [-1]
	sa = sorted(a)
	r = sa[-1] - sa[0]
	for i in range(1, n + 1):
		if sa[i] == sa[i - 1]:
			continue
		mi = sa[i]
		b = []
		c = 0
		for j in range(n + 1):
			if a[j] < mi:
				if j - c >= k:
					b += sorted(a[c:j])[:j - c - k + 1]
				c = j + 1
		if len(b) < q:
			continue
		b.sort()
		t = b[q - 1] - mi
		if r > t:
			r = t
	return r
print(main())


def main():
	(N, K, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	ans = float('inf')
	for X in A:
		targets = []
		t = []
		for a in A:
			if a >= X:
				t.append(a)
			else:
				if len(t) >= K:
					targets += sorted(t)[:len(t) - K + 1]
				t = []
		if len(t) >= K:
			targets += sorted(t)[:len(t) - K + 1]
		targets.sort()
		if len(targets) >= Q:
			ans = min(targets[Q - 1] - targets[0], ans)
	print(ans)
main()


(N, K, Q, *A) = map(int, open(0).read().split())
ans = 10 ** 10
for i in range(N - K + 1):
	c = min(A[i:i + K])
	ls = []
	x = []
	for d in A:
		if d >= c:
			x.append(d)
		else:
			ls.append(x)
			x = []
	ls.append(x)
	m = []
	for x in ls:
		x.sort()
		m += x[:max(len(x) - K + 1, 0)]
	if len(m) < Q:
		continue
	m.sort()
	y = m[Q - 1]
	ans = min(ans, y - c)
print(ans)


(N, K, Q) = map(int, input().split())
a = list(map(int, input().split()))
ans = float('inf')
for i in range(N):
	tmp = []
	rec = []
	for j in range(N):
		if a[i] <= a[j]:
			tmp.append(a[j])
		else:
			if len(tmp) >= K:
				tmp = sorted(tmp)
				rec += tmp[:len(tmp) - K + 1]
			tmp = []
	if len(tmp) >= K:
		tmp = sorted(tmp)
		rec += tmp[:len(tmp) - K + 1]
	if Q <= len(rec):
		rec = sorted(rec)
		ans = min(ans, rec[Q - 1] - rec[0])
print(ans)


import heapq

def main():
	(_, k, q) = map(int, input().split())
	a = list(map(int, input().split()))
	idx = make_index(a)
	groups = [(0, len(a))]
	m = float('inf')
	for y in sorted(set(a)):
		xs = []
		for (start, stop) in groups:
			xs.extend(nsmallest(min(stop - start - k + 1, q), a, start, stop))
		if len(xs) < q:
			break
		xxs = heapq.nsmallest(q, xs)
		x = xxs[-1]
		m = min(m, x - y)
		groups = split_groups(idx[y], groups, k)
	print(m)
MEMO = dict()

def nsmallest(n, a, start, stop):
	global MEMO
	key = (n, id(a), start, stop)
	if key in MEMO:
		return MEMO[key]
	val = heapq.nsmallest(n, a[start:stop])
	MEMO[key] = val
	return val

def split_groups(pivots, groups, k):
	gs = []
	i = 0
	for (start, stop) in groups:
		while i < len(pivots) and pivots[i] < start:
			i += 1
		while i < len(pivots) and pivots[i] <= stop:
			if pivots[i] - start >= k:
				gs.append((start, pivots[i]))
			start = pivots[i] + 1
			i += 1
		if stop - start >= k:
			gs.append((start, stop))
	return gs

def make_index(a):
	idx = dict()
	for (i, x) in enumerate(a):
		if x in idx:
			idx[x].append(i)
		else:
			idx[x] = [i]
	return idx
main()


import sys
input = sys.stdin.readline

def main():
	(n, k, q) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [[v, i] for (i, v) in enumerate(a)]
	b.sort()
	index = [0] * n
	for i in range(n):
		index[i] = b[i][1]
	judge = [[] for i in range(n)]
	already = [-1, n]
	for i in range(n):
		for j in range(len(already) - 1):
			key = a[already[j] + 1:already[j + 1]]
			if len(key) >= k:
				judge[i].append(key)
		already.append(index[i])
		already.sort()
	ans = 1000000000.0
	for i in range(n):
		if not judge[i]:
			break
		m = b[i][0]
		sub = []
		for values in judge[i]:
			values.sort()
			for j in range(len(values) - k + 1):
				sub.append(values[j])
		sub.sort()
		if len(sub) < q:
			break
		M = sub[q - 1]
		ans = min(ans, M - m)
	print(ans)
main()


(N, K, Q) = list(map(int, input().split()))
a = list(map(int, input().split()))
ai = []
for i in range(N):
	ai.append([a[i], i])
ai.sort()
ans = ai[Q - 1][0] - ai[0][0]
for cant in range(N - Q):
	rannum = [-1] * (cant + 2)
	rannum[0] = 0
	indlis = [0] * N
	for i in range(cant + 1):
		(na, nind) = ai[i]
		indlis[nind] += 1
	for i in range(N):
		if i != N - 1:
			indlis[i + 1] += indlis[i]
		rannum[indlis[i]] += 1
	ncat = []
	for i in range(cant + 1, N):
		(na, nind) = ai[i]
		if rannum[indlis[nind]] >= K:
			ncat.append(na)
			rannum[indlis[nind]] -= 1
		if len(ncat) == Q:
			ans = min(ans, ncat[-1] - ncat[0])
			break
print(ans)


import sys
input = sys.stdin.readline
from heapq import *
(N, K, Q) = map(int, input().split())
A = [int(x) for x in input().split()]
R_to_L = [None] * (N + 10)
L_to_R = [None] * (N + 10)
rest = [[] for _ in range(N + 10)]
from_max = sorted(enumerate(A), key=lambda x: x[1], reverse=True)
INF = 10 ** 18
get_reverse = [-INF] * Q

def push_K(arr, x):
	if len(arr) < K - 1:
		heappush(arr, x)
	else:
		y = heappushpop(arr, x)
		heappushpop(get_reverse, -y)
answer = INF
for (i, x) in from_max:
	left = R_to_L[i - 1]
	right = L_to_R[i + 1]
	if left is None:
		left = i
		push_K(rest[left], x)
	else:
		push_K(rest[left], x)
	if right is None:
		right = i
	else:
		for r in rest[i + 1]:
			push_K(rest[left], r)
	R_to_L[right] = left
	L_to_R[left] = right
	score = -get_reverse[0] - x
	if answer > score:
		answer = score
print(answer)


def main():
	import sys
	input = sys.stdin.readline
	(n, k, q) = map(int, input().split())
	a = list(map(int, input().split()))
	res = 10 ** 9
	for e in a:
		tank = []
		new = []
		for je in a:
			if e <= je:
				tank.append(je)
			else:
				if len(tank) >= k:
					tank.sort()
					for i in range(len(tank) - k + 1):
						new.append(tank[i])
				tank = []
		if len(tank) >= k:
			tank.sort()
			for i in range(len(tank) - k + 1):
				new.append(tank[i])
		new.sort()
		if len(new) > q - 1:
			res = min(res, new[q - 1] - e)
	print(res)
main()


def main():
	from collections import Counter as ct
	(n, k, q) = map(int, input().split())
	a = list(map(int, input().split()))
	c = ct(a).keys()
	a += [0]
	ans = []
	for i in c:
		temp = []
		temp2 = []
		for j in a:
			if j >= i:
				temp2.append(j)
			elif temp2:
				temp2.sort()
				if len(temp2) >= k:
					for l in temp2[:len(temp2) - k + 1]:
						temp.append(l)
				temp2 = []
		if len(temp) >= q:
			temp.sort()
			ans.append(temp[q - 1] - i)
	print(min(ans))
main()


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
(n, k, q) = list(map(int, input().split()))
a = list(map(int, input().split()))
arg = [(num, i) for (i, num) in enumerate(a)]
arg.sort()

def sub(x):
	index = [item[1] for item in arg[:x]]
	index.sort()
	index.append(n)
	vals = []
	prv = 0
	for ind in index:
		if ind - prv >= k:
			vals.extend(sorted(a[prv:ind])[:ind - prv - k + 1])
		prv = ind + 1
		if prv >= n:
			break
	if len(vals) < q:
		return None
	else:
		vals.sort()
		return vals[q - 1] - arg[x][0]
ans = float('inf')
for i in range(n):
	res = sub(i)
	if res is not None:
		ans = min(ans, res)
print(ans)


import sys
from heapq import *
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():
	(n, k, q) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	res = f_inf
	for a in A:
		section = []
		tmp = []
		for b in A:
			if b < a:
				if len(tmp) >= k:
					section.append(tmp)
				tmp = []
			else:
				heappush(tmp, b)
		if len(tmp) >= k:
			section.append(tmp)
		kouho = []
		for sec in section:
			while len(sec) >= k:
				kouho.append(heappop(sec))
		if len(kouho) >= q:
			kouho.sort()
			x = kouho[q - 1]
			y = kouho[0]
			res = min(res, x - y)
	print(res)

def __starting_point():
	resolve()
__starting_point()


(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
ans = 10 ** 18
for Y in set(A):
	L = []
	l = []
	for i in range(N):
		if A[i] < Y:
			L.append(l)
			l = []
		else:
			l.append(A[i])
	L.append(l)
	l2 = []
	for l in L:
		if len(l) <= K - 1:
			continue
		l.sort()
		for i in range(len(l) - K + 1):
			l2.append(l[i])
	if len(l2) < Q:
		continue
	l2.sort()
	X = l2[Q - 1]
	ans = min(ans, X - Y)
print(ans)


(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))

def find_maximum(y):
	C = [[]]
	for a in A:
		if a < y:
			if len(C[-1]) > 0:
				C.append([])
		else:
			C[-1].append(a)
	cand_x = []
	for Ci in C:
		m = len(Ci)
		if m >= K:
			Ci.sort()
			cand_x += Ci[:m - K + 1]
	if len(cand_x) >= Q:
		cand_x.sort()
		return (cand_x[Q - 1], cand_x[0])
	else:
		return (10 ** 18, 0)
ans = 10 ** 18
for a in A:
	(x, y) = find_maximum(a)
	ans = min(ans, x - y)
print(ans)


(n, k, q) = map(int, input().split())
alist = list(map(int, input().split()))
ans = None
if q == 1:
	print(0)
else:
	for (i, a) in enumerate(alist):
		spla = []
		preva = -1
		ailist = alist[:i] + alist[i + 1:]
		for (j, _a) in enumerate(ailist):
			if _a < a:
				spla.append(ailist[preva + 1:j])
				preva = j
		if not preva == len(ailist) - 1:
			spla.append(ailist[preva + 1:])
		conda = []
		for sa in spla:
			if len(sa) >= k:
				conda.extend(list(sorted(sa))[:len(sa) - k + 1])
		if len(conda) < q - 1:
			continue
		else:
			y = list(sorted(conda))[q - 2]
			if ans is None or ans > y - a:
				ans = y - a
	print(ans)


(N, K, Q) = map(int, input().split())
(*A,) = map(int, input().split())
import heapq
ans = 10 ** 10
A.append(-1)
for y in A:
	if y == -1:
		break
	(p, q) = ([], [])
	for a in A:
		if a >= y:
			heapq.heappush(p, a)
		else:
			for i in range(max(0, len(p) - (K - 1))):
				heapq.heappush(q, heapq.heappop(p))
			p = []
	if len(q) < Q:
		continue
	x = -1
	for i in range(Q):
		x = heapq.heappop(q)
	ans = min(ans, x - y)
print(ans)


(n, k, q) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
ans = float('inf')
for i in range(n):
	y = a[i]
	c = []
	c_k = []
	for j in range(n):
		if a[j] >= y:
			c_k.append(a[j])
		else:
			c.append(c_k)
			c_k = []
	else:
		c.append(c_k)
	d = []
	for j in c:
		if len(j) >= k:
			j.sort()
			for l in range(len(j) - k + 1):
				d.append(j[l])
	if len(d) >= q:
		d.sort()
		ans = min(ans, d[q - 1] - d[0])
print(ans)


from collections import defaultdict
import heapq
(n, k, q) = map(int, input().split())
a = list(map(int, input().split()))
ok = [0] * n
d = defaultdict(lambda : set())
h = []
for i in range(k - 1):
	heapq.heappush(h, [a[i], i])
	d[a[i]].add(i)
for i in range(k - 1, n):
	heapq.heappush(h, [a[i], i])
	d[a[i]].add(i)
	while h:
		if h[0][1] >= i - k + 1:
			break
		heapq.heappop(h)
	m = list(d[h[0][0]])
	for j in m:
		if j >= i - k + 1:
			ok[j] = 1
		d[h[0][0]].remove(j)
ans = 1145141919810
for i in range(n):
	if ok[i]:
		(s, t) = ([], [])
		for j in range(n):
			if a[i] > a[j]:
				s.sort()
				for l in range(max(0, len(s) - k + 1)):
					t.append(s[l])
				s = []
			else:
				s.append(a[j])
		s.sort()
		for l in range(max(0, len(s) - k + 1)):
			t.append(s[l])
		t.sort()
		if len(t) >= q:
			ans = min(ans, t[q - 1] - t[0])
print(ans)


from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
	return int(input())

def reads():
	return [int(x) for x in input().split()]
INF = 1 << 60
(N, K, Q) = reads()
A = reads()
A.append(-INF)

def getlub(y):
	v = []
	l = 0
	for i in range(N + 1):
		if A[i] < y:
			w = A[l:i]
			w.sort()
			if len(w) >= K - 1:
				v.extend(w[:len(w) - K + 1])
			l = i + 1
	v.sort()
	return v[Q - 1] if len(v) >= Q else INF
ans = INF
for Y in A[:-1]:
	X = getlub(Y)
	ans = min(ans, X - Y)
print(ans)


(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
ans = float('inf')
for Y in A:
	B = []
	tmp = []
	for a in A:
		if a < Y:
			if tmp:
				B.append(tmp)
				tmp = []
		else:
			tmp.append(a)
	if tmp:
		B.append(tmp)
		tmp = []
	cand = []
	B = [sorted(b) for b in B]
	for b in B:
		r = max(len(b) - K + 1, 0)
		cand += b[:r]
	cand = sorted(cand)
	if len(cand) >= Q:
		X = cand[Q - 1]
		ans = min(ans, X - Y)
print(ans)


(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
R = sorted(set(A))
ans = 10 ** 9
for i in range(len(R)):
	temp = []
	temp2 = []
	l = 0
	for j in range(N):
		if A[j] < R[i]:
			if l >= K:
				temp += sorted(temp2)[:min(l, max(0, l - K + 1))]
			temp2 = []
			l = 0
		else:
			temp2.append(A[j])
			l += 1
	if l >= K:
		temp += sorted(temp2)[:min(l, max(0, l - K + 1))]
	if len(temp) > Q - 1:
		temp = sorted(temp)
		ans = min(ans, temp[Q - 1] - R[i])
	else:
		break
print(ans)


import sys
input = sys.stdin.readline

def I():
	return int(input())

def MI():
	return list(map(int, input().split()))

def LI():
	return list(map(int, input().split()))

def main():
	mod = 10 ** 9 + 7
	(N, K, Q) = MI()
	A = LI()
	inf = 10 ** 10
	if Q == 1:
		print(0)
		return ()

	def calc(Y):
		L = []
		temp = []
		for a in A:
			if a >= Y:
				temp.append(a)
			else:
				if len(temp) >= K:
					temp.sort()
					if K > 1:
						L += temp[:-(K - 1)]
					else:
						L += temp
				temp = []
		if len(temp) >= K:
			temp.sort()
			if K > 1:
				L += temp[:-(K - 1)]
			else:
				L += temp
		L.sort()
		if len(L) >= Q:
			return L[Q - 1]
		else:
			return inf
	ans = inf
	for b in A:
		y = b
		x = calc(y)
		temp = x - y
		ans = min(ans, temp)
	print(ans)
main()


import heapq
(N, K, Q) = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
sA = sorted(A)
A += [-1]
ans = float('inf')
for amin in sA:
	cand = []
	dp = []
	for i in range(N + 1):
		a = A[i]
		if a >= amin:
			heapq.heappush(dp, a)
		if len(dp) and a < amin:
			m = len(dp) - K + 1
			for _ in range(m):
				heapq.heappush(cand, heapq.heappop(dp))
			dp = []
	y = float('inf')
	if len(cand) < Q:
		break
	for _ in range(Q - 1):
		heapq.heappop(cand)
	ans = min(ans, heapq.heappop(cand) - amin)
print(ans)


import bisect
(N, K, Q) = [int(i) for i in input().split()]
A = [(int(v), i) for (i, v) in enumerate(input().split())]
A.sort()
B = [0] * N
for i in range(N):
	B[A[i][1]] = i
C = [A[B[i]][0] for i in range(N)]
Candi = set(range(N))
ctr = 0
ans = []
rng = [-1, N]
while len(Candi) >= Q:
	T = sorted(Candi)
	ans.append((list(T)[0], list(T)[Q - 1]))
	x = B.index(ctr)
	st = bisect.bisect_left(rng, x)
	Candi = Candi - set(sorted(B[rng[st - 1] + 1:x] + [2002], reverse=1)[:K]) - set(sorted(B[x:rng[st]] + [2002], reverse=1)[:K]) - set([B[x]])
	bisect.insort_left(rng, x)
	ctr += 1
print(min([A[j][0] - A[i][0] for (i, j) in ans]))


from itertools import accumulate

def inpl():
	return map(int, input().split())
(N, K, Q) = inpl()
A = ' ' + input()
S = sorted(map(int, A.split()))
ans = S[Q - 1] - S[0]
S = S[::-1]
while S:
	s = S.pop()
	A = A.replace(' {} '.format(s), ' x ')
	OK = 0
	Que = A.split('x')
	tmp = []
	for q in Que:
		tmp.extend(sorted([int(x) for x in q.split()])[::-1][K - 1:])
	if len(tmp) < Q:
		break
	tmp = sorted(tmp)
	ans = min(ans, tmp[Q - 1] - tmp[0])
print(ans)


import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
(N, K, Q) = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))
if Q == 1:
	print(0)
	exit()

def argsort(li, key=None, reverse=False):
	return [i for (_, i) in sorted([(a, i) for (i, a) in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse)]
idx = argsort(A)
used = [False] * N
ans = INF
for min_i in idx:
	groups = [[]]
	for i in range(N):
		if used[i]:
			if groups[-1]:
				groups.append([])
		else:
			groups[-1].append(A[i])
	nums = []
	for group in groups:
		if len(group) >= K:
			group.sort()
			nums += group[:len(group) - K + 1]
	if len(nums) < Q:
		break
	nums.sort()
	ans = min(ans, nums[Q - 1] - nums[0])
	used[min_i] = True
print(ans)


(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
B = sorted(A)
L = [[i, B[i + Q - 1] - B[i]] for i in range(N - Q + 1)]
sL = sorted(L, key=lambda x: x[1])
if Q == 1:
	print(0)
	exit()
if Q == N - K + 1:
	print(L[0][1])
	exit()
if K == 1:
	print(sL[0][1])
	exit()
if sL[0][0] == 0:
	print(sL[0][1])
	exit()
if sL[0][1] == sL[len(sL) - 1][1]:
	print(sL[0][1])
	exit()
for (key, value) in sL:
	max_value = B[key + Q - 1]
	min_value = B[key]
	C = [i if i >= min_value else None for i in A]
	i = 0
	j = 0
	count = 0
	min_OK = max_OK = False
	while i < N:
		if not C[i]:
			i += 1
			continue
		j = i + 1
		while j < N:
			if not C[j]:
				break
			j += 1
		tmp = j - i - K + 1
		if tmp < 1:
			i = j + 1
			continue
		sC = sorted(C[i:j])
		if not min_OK and sC[0] == min_value:
			min_OK = True
		if not max_OK and max_value in sC[0:tmp]:
			max_OK = True
		count += tmp - len([i for i in sC[:tmp] if i > max_value])
		i = j + 1
	if min_OK and max_OK and (count >= Q):
		print(value)
		exit()
print(L[0][1])


def examC():
	N = I()
	S = SI()
	E = S.count('E')
	W = N - E
	curW = 0
	curE = 0
	ans = N - 1
	for i in range(N):
		if S[i] == 'W':
			curW += 1
		cur = N - 1 - (W - curW) - curE
		if S[i] == 'E':
			curE += 1
		ans = min(ans, cur)
	print(ans)
	return

def examD():
	N = I()
	A = LI()
	cur = [0] * 21
	k = 0
	ans = 0
	flag = True
	for i in range(N):
		for j in range(21):
			if cur[j] >= 2:
				a = A[i]
				for l in range(21):
					if a & 1 << l == 1 << l:
						cur[l] -= 1
				continue
		flag = True
		while k < N:
			a = A[k]
			for j in range(21):
				if a & 1 << j == 1 << j:
					if cur[j] >= 1:
						flag = False
						break
			if flag:
				for j in range(21):
					if a & 1 << j == 1 << j:
						cur[j] += 1
				k += 1
			if not flag:
				break
		ans += k - i
		a = A[i]
		for j in range(21):
			if a & 1 << j == 1 << j:
				cur[j] -= 1
	print(ans)
	return

def examE():
	(N, K, Q) = LI()
	A = LI()
	ans = inf
	for i in range(N):
		a = A[i]
		curL = []
		l = 0
		r = 0
		while l < N:
			while r < N:
				if A[r] < a:
					break
				r += 1
			if l < r:
				curL.append(A[l:r])
			l = r + 1
			r = l
		cur = []
		for v in curL:
			if len(v) >= K:
				v.sort()
				for j in range(len(v) - K + 1):
					cur.append(v[j])
		if len(cur) >= Q:
			cur.sort()
			now = cur[Q - 1] - cur[0]
			ans = min(ans, now)
	print(ans)
	return
import sys, copy, bisect, itertools, heapq, math
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, ALPHABET
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
alphabet = [chr(ord('a') + i) for i in range(26)]
ALPHABET = [chr(ord('A') + i) for i in range(26)]
examE()


import sys
input = sys.stdin.readline
(n, k, q) = map(int, input().split())
A = list(map(int, input().split())) + [-1]
ans = float('inf')
for a in A:
	L = []
	K = []
	for t in A:
		if t >= a:
			L.append(t)
		else:
			L.sort()
			for c in range(len(L) - k + 1):
				K.append(L[c])
			L = []
	K.sort()
	if len(K) < q:
		continue
	else:
		y = K[q - 1]
		ans = min(ans, y - a)
print(ans)


import sys
from heapq import *
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
res = 0

def resolve():
	(n, k, q) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	res = f_inf
	for i in range(n):
		section = []
		pick = []
		for j in range(n):
			if A[j] < A[i]:
				l = len(section) - k + 1
				for _ in range(l):
					pick.append(heappop(section))
				section.clear()
			else:
				heappush(section, A[j])
		l = len(section) - k + 1
		for _ in range(l):
			pick.append(heappop(section))
		if len(pick) >= q:
			pick.sort()
			res = min(res, pick[q - 1] - pick[0])
	print(res)

def __starting_point():
	resolve()
__starting_point()


(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
D = set()
for i in range(N):
	D.add(A[i])
D = list(D)
ans = float('inf')
for Y in D:
	T = []
	tmp = []
	for j in range(N):
		if A[j] >= Y:
			tmp.append(A[j])
		else:
			if len(tmp) >= K:
				tmp = sorted(tmp)
				T += tmp[:len(tmp) - K + 1]
			tmp = []
	if len(tmp) >= K:
		tmp = sorted(tmp)
		T += tmp[:len(tmp) - K + 1]
	if len(T) >= Q:
		T = sorted(T)
		T = T[:Q]
		ans = min(ans, T[-1] - T[0])
print(ans)


from heapq import *
(N, K, Q) = map(int, input().split())
a = list(map(int, input().split()))
b = [None] * (N + 2)
x = []

def merge(q1, q2):
	if q1 < q2:
		(q1, q2) = (q2, q1)
	s = q1[0] + q2[0]
	while q2[1]:
		add(q1, heappop(q2[1]))
	q1[0] = s
	return q1

def add(q, v):
	q[0] += 1
	w = push(q[1], K - 1, v)
	if w:
		push(x, Q, -w)

def push(q, m, v):
	if len(q) < m:
		heappush(q, v)
		return
	return heappushpop(q, v)
r = 10 ** 9
for i in sorted(range(1, N + 1), key=lambda x: -a[x - 1]):
	if b[i - 1] and b[i + 1]:
		(s, t) = (b[i - 1][0], b[i + 1][0])
		b[i - s] = b[i + t] = merge(b[i - 1], b[i + 1])
		add(b[i - s], a[i - 1])
		b[i] = 1
	elif b[i - 1]:
		add(b[i - 1], a[i - 1])
		b[i] = b[i - 1]
	elif b[i + 1]:
		add(b[i + 1], a[i - 1])
		b[i] = b[i + 1]
	else:
		b[i] = [0, []]
		add(b[i], a[i - 1])
	if len(x) == Q:
		r = min(r, -x[0] - a[i - 1])
print(r)


(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
INF = 10 ** 20

def f(b):
	i = 0
	T = []
	while i < N:
		S = []
		while i < N and A[i] >= b:
			S.append(A[i])
			i += 1
		if len(S) >= K:
			T.extend(sorted(S)[:len(S) - K + 1])
		i += 1
	return sorted(T)[Q - 1] if len(T) >= Q else INF
ans = min((f(a) - a for a in A))
print(ans)


import sys
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
YesNo = lambda b: bool([print('Yes')] if b else print('No'))
YESNO = lambda b: bool([print('YES')] if b else print('NO'))
int1 = lambda x: int(x) - 1
(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
if Q == 1:
	print(0)
	return ()
ans = INF
for (i, Y) in enumerate(A):
	seqs = []
	tmp = []
	for (j, x) in enumerate(A):
		if i == j:
			continue
		if x >= Y:
			tmp.append(x)
		elif tmp:
			tmp.sort()
			seqs.append(tmp)
			tmp = []
	if tmp:
		tmp.sort()
		seqs.append(tmp)
	l = []
	for seq in seqs:
		if len(seq) >= K:
			l.extend(seq[:len(seq) - K + 1])
	l.sort()
	if len(l) >= Q - 1:
		X = l[Q - 2]
		ans = min(ans, X - Y)
print(ans)


(n, k, q) = map(int, input().split())
a = list(map(int, input().split()))
ans = 10 ** 15
for i in range(n):
	x = a[i]
	y_cand = []
	lis = []
	for j in range(n):
		if a[j] < x:
			if len(lis) - k + 1 >= 0:
				lis.sort()
				y_cand.extend(lis[:len(lis) - k + 1])
			lis = []
		else:
			lis.append(a[j])
	if len(lis) - k + 1 >= 0:
		lis.sort()
		y_cand.extend(lis[:len(lis) - k + 1])
	if len(y_cand) >= q:
		y_cand.sort()
		y = y_cand[q - 1]
		ans = min(ans, abs(x - y))
print(ans)


import sys, collections, bisect, math, itertools, heapq
from fractions import gcd
(n, k, q) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
aa = sorted(a)
a += [0]
ans = 10 ** 9 + 1
mmm = 0
for (i, m) in enumerate(aa):
	if mmm == m:
		continue
	hh = []
	mae = 0
	for (j, aj) in enumerate(a):
		if aj < m:
			h = a[mae:j]
			heapq.heapify(h)
			for _ in range(j - mae - k + 1):
				hh.append(heapq.heappop(h))
			mae = j + 1
	mmm = m
	if len(hh) < q:
		break
	else:
		hh.sort()
		ans = min(ans, hh[q - 1] - hh[0])
print(ans)


import heapq
(N, K, Q) = map(int, input().split())
A = list(map(int, input().split()))
N0 = 2 ** (N - 1).bit_length()
INF = 2 ** 31 - 1
seg_min = [INF] * (2 * N0)
seg_min_idx = [0] * (2 * N0)

def update(idx, value):
	idx += N0 - 1
	seg_min[idx] = value
	seg_min_idx[idx] = idx
	while idx > 0:
		idx = (idx - 1) // 2
		seg_min[idx] = min(seg_min[idx * 2 + 1], seg_min[idx * 2 + 2])
		seg_min_idx[idx] = seg_min_idx[idx * 2 + 1] if seg_min[idx * 2 + 1] <= seg_min[idx * 2 + 2] else seg_min_idx[idx * 2 + 2]

def query(first, last):
	first += N0 - 1
	last += N0 - 1
	ret = INF
	min_idx = 0
	while first <= last:
		if not first & 1:
			if seg_min[first] < ret:
				min_idx = seg_min_idx[first]
			ret = min(ret, seg_min[first])
		if last & 1:
			if seg_min[last] < ret:
				min_idx = seg_min_idx[last]
			ret = min(ret, seg_min[last])
		first = first // 2
		last = last // 2 - 1
	min_idx -= N0 - 1
	return (ret, min_idx)
for (i, x) in enumerate(A):
	update(i, x)
A_index = []
left_right_used = []
for (i, x) in enumerate(A):
	A_index.append((x, i))
	left_right_used.append([i, i, 0])
A_index.sort(key=lambda a: a[0], reverse=True)
pq = []
ans = 10 ** 10
for i in range(N):
	left_used_flag = 0
	right_used_flag = 0
	index = A_index[i][1]
	left_right_used[index][2] = 1
	if index - 1 >= 0:
		if left_right_used[index - 1][2] == 1:
			left_used_flag = 1
	if index + 1 < N:
		if left_right_used[index + 1][2] == 1:
			right_used_flag = 1
	if left_used_flag == 1 and right_used_flag == 1:
		leftmost = left_right_used[index - 1][0]
		rightmost = left_right_used[index + 1][1]
	elif left_used_flag == 1 and right_used_flag == 0:
		leftmost = left_right_used[index - 1][0]
		rightmost = index
	elif left_used_flag == 0 and right_used_flag == 1:
		leftmost = index
		rightmost = left_right_used[index + 1][1]
	else:
		leftmost = rightmost = index
	num_old = max(0, left_right_used[leftmost][1] - left_right_used[leftmost][0] - K + 2) * left_used_flag + max(0, left_right_used[rightmost][1] - left_right_used[rightmost][0] - K + 2) * right_used_flag
	left_right_used[leftmost][1] = rightmost
	left_right_used[rightmost][0] = leftmost
	num_new = max(0, left_right_used[leftmost][1] - left_right_used[leftmost][0] - K + 2)
	num_add = num_new - num_old
	for j in range(num_add):
		(range_min, min_index) = query(leftmost, rightmost)
		update(min_index, 10 ** 10)
		heapq.heappush(pq, range_min * -1)
	for j in range(num_add):
		if len(pq) > Q:
			heapq.heappop(pq)
	if len(pq) == Q:
		maximum = heapq.heappop(pq) * -1
		ans_new = maximum - A[index]
		ans = min(ans, ans_new)
		heapq.heappush(pq, maximum * -1)
print(ans)


(n, k, q) = map(int, input().split())
a = [0] * (n + 1)
b = list(map(int, input().split()))
for i in range(1, n + 1):
	a[i] = b[i - 1]

def check(l, r):
	cnt = 0
	ln = 0
	res = 0
	for i in range(1, n + 1):
		if a[i] < l:
			res += min(cnt, max(0, ln - k + 1))
			ln = 0
			cnt = 0
		else:
			ln += 1
			if a[i] <= r:
				cnt += 1
	res += min(cnt, max(0, ln - k + 1))
	if res >= q:
		return True
	return False
l = 0
r = 1000000000
res = 1000000000
while l <= r:
	m = (l + r) // 2
	ok = 0
	for i in range(1, n + 1):
		ok |= check(a[i] - m, a[i])
	if ok == 1:
		r = m - 1
		res = m
	else:
		l = m + 1
print(res)


def solve(N, K, Q, As, X):
	mins = []
	tmp = []
	for A in As:
		if A >= X:
			tmp.append(A)
		else:
			if len(tmp) >= K:
				tmp.sort()
				mins.extend(tmp[:len(tmp) - K + 1])
			tmp = []
	if len(tmp) >= K:
		tmp.sort()
		mins.extend(tmp[:len(tmp) - K + 1])
	if len(mins) < Q:
		return None
	mins.sort()
	taken = mins[:Q]
	return taken[-1] - taken[0]
(N, K, Q) = map(int, input().split())
As = [int(x) for x in input().split()]
ans = -1
for A in As:
	cand = solve(N, K, Q, As, A)
	if cand is not None and (ans == -1 or ans > cand):
		ans = cand
print(ans)