Problem:
 Score : 600 points    Problem Statement 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 1 5 3 2
4 3 1 5 2      Sample Output 1 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 .       Sample Input 2 10 1 6
1 1 2 3 5 8 13 21 34 55      Sample Output 2 7       Sample Input 3 11 7 5
24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784      Sample Output 3 451211184

Solution (Python):
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)

Solution (Python):

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)

Solution (Python):

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 sorted(A))


print(ans)

Solution (Python):
def main():
    n,k,q,*a=map(int,open(0).read().split())
    s=sorted
    m=1e18
    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)
main()

Solution (Python):
n,k,q,*a=map(int,open(0).read().split())
s=sorted
m=1e18
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])],[]))
    if len(l)>=q:m=min(m,l[q-1]-b)
print(m)

Solution (Python):
n,k,q,*a=map(int,open(0).read().split())
s=sorted
m=1e18
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)


if __name__ == "__main__":
    main()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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 in range(N):
        if a[i] >= 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)

Solution (Python):
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)

Solution (Python):

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)

Solution (Python):


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)

Solution (Python):
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
        else:
            if 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)

Solution (Python):



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))


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
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]))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
N, K, Q = map(int, input().split())
a = list(map(int, input().split()))

d = [a]
a = sorted(a)
a.sort()
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 = sorted(a)

  if len(a) < Q:
    break
  else:
    ans = min(ans, a[Q-1] - a[0])

print(ans)

Solution (Python):
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 = sorted(a)

  if len(a) < Q:
    break
  else:
    ans = min(ans, a[Q-1] - a[0])

print(ans)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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()

now_max_value = -1
now_min_value = -1
now_min_XY = int(1e10)

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()
    now_min_XY = min(now_min_XY,now_max_value - now_min_value)
    now_max_value = -1
    now_min_value = -1

print(L[0][1])

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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(set(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)
    lists = new_lists

print(ans)

Solution (Python):
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(set(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)

Solution (Python):
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)

Solution (Python):
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)