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

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

Solution (Python):
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(stop - start - k + 1, 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()

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

Solution (Python):
import heapq

def main():
    _, k, q = map(int, input().split())
    a = tuple(map(int, input().split()))

    gs = [a]
    m = float('inf')
    for y in sorted(set(a)):
        gs = groups(gs, y, k)
        x = find_x(gs, y, k, q)
        if x is None:
            break
        m = min(m, x - y)
    
    print(m)

def find_x(gs, y, k, q):
    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(gs, m, k):
    new_gs = []
    for g in gs:
        new_gs.extend(groups_1(g, m, k))
    return new_gs

def groups_1(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()

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

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

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

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

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

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

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

Solution (Python):

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)

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):
from collections import defaultdict
def main():
    n, k, q = map(int, raw_input().split())
    a = map(int, raw_input().split())
    d = defaultdict(list)
    for i, x in enumerate(a):
        d[x].append(i)
    a.append(-1)
    ans = 1001001001
    for x in sorted(d.keys()):
        p = 0
        b = []
        s = 0
        for j, y in enumerate(a):
            if y < x:
                if j - p >= k:
                    t = a[p:j]
                    t.sort()
                    b.extend(t[:j-p-k+1])
                p = j + 1
        if len(b) >= q:
            b.sort()
            ans = min(ans, b[q-1] - x)
        else:
            break
    print ans
main()