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):
n,k,q = 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 = []
    else:
        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)

Solution (Python):
n,k,q = 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 = []
    else:
        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)

Solution (Python):
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=map(int,input().split())
x=list(map(int,input().split()))
print(main(n,k,q,x))

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

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

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

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

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


    
if __name__ == "__main__":
    main()

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


    
if __name__ == "__main__":
    main()

Solution (Python):
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):
    """0,1,...,x-1番目は使わない場合において、X-Yの値
    """
    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)

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

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

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

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

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

Solution (Python):
n,k,q=map(int, input().split())
if q==1:
    print(0)
    exit()
*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)

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

Solution (Python):
import bisect
n,k,q = map(int,input().split())
a = list(map(int,input().split()))
if q == 1:
  print(0)
  exit()
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))

Solution (Python):
n, k, q = 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)

Solution (Python):
n, k, q = map(int, input().split())
a = list(map(int, input().split()))

ans = 10 ** 10
for i, y in enumerate(a):
    li = []
    l = 0
    cnd = []
    l_cnd = 0
    for j, x in enumerate(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)

Solution (Python):
n, k, q = map(int, input().split())
a = list(map(int, input().split()))

if q == 1:
    print(0)
    exit()

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)

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

if __name__ == '__main__':
    main()

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


if __name__ == "__main__":
    print(main())

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

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

Solution (Python):
def main():
    def calc_x_y(mi):
        """取り除いた要素の最小値がmiとなるように
        操作をQ回行えるか
        行える -> Q回の操作で取り除いた要素の最大値 - mi
        行えない -> -1
        """

        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 = map(int, input().split())
    *a, = 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)


if __name__ == '__main__':
    main()

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

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

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

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

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

Solution (Python):
N, K, Q = 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.extend(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)

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

Solution (Python):
N, K, Q = 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)

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

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

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

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

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

Solution (Python):

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)

if __name__ == "__main__":
    main()

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

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

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

Solution (Python):


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)
        if m-K+1 >= 1:
            li.sort()
            C += li[:m-K+1]
    
    C.sort()
    if len(C) < Q:
        continue
    y = C[Q-1]
    ans = min(ans, y - x)
print(ans)

Solution (Python):


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)

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

Solution (Python):
n,k,q = map(int, input().split())
a = list(map(int, input().split()))

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])
    return ret

ans = 10**10

for b in set(a):
    lis = parse(b)
    if len(lis) < q:
        continue
    lis.sort()
    ans_tmp = lis[q-1] - lis[0]
    ans = min(ans, ans_tmp)

print(ans)