output_description: Print the smallest possible value of X-Y.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N K Q
      A_1 A_2 ... A_N
attempt: 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)
  
problem_description: 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.
samples: [{"input": "5 3 2\n    4 3 1 5 2", "output": "1\n    \n\nIn the first operation, whichever contiguous subsequence of length 3 we\nchoose, the minimum element in it is 1. Thus, the first operation removes\nA_3=1 and now we have A=(4,3,5,2). In the second operation, it is optimal to\nchoose (A_2,A_3,A_4)=(3,5,2) as the contiguous subsequence of length 3 and\nremove A_4=2. In this case, the largest element removed is 2, and the smallest\nis 1, so their difference is 2-1=1.\n\n* * *"}, {"input": "10 1 6\n    1 1 2 3 5 8 13 21 34 55", "output": "7\n    \n\n* * *"}, {"input": "11 7 5\n    24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784", "output": "451211184"}]