Problem: Takahashi made N problems for competitive programming. The problems are numbered 1 to N, and the difficulty of Problem i is represented as an integer d_i (the higher, the harder).  He is dividing the problems into two categories by choosing an integer K, as follows:    * A problem with difficulty K or higher will be _for ARCs_.   * A problem with difficulty lower than K will be _for ABCs_.  How many choices of the integer K make the number of problems for ARCs and the number of problems for ABCs the same?

Submission attempts (in order):
def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr
 
    
    # ref = random.choice(arr)
    ref = arr[0]
    ref_count = 0
 
    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right
n=input()
S=map(int,input().split())
S=quick_sort(S)
word=int(int(n)/2)
s=int(S[word])-int(S[word-1])
s2=int(S[word+1])-int(S[word])
print(s)

def _quick_sort(array, left, right):
    if left >= right: return

    
    pivot = median(array[left], array[(left + (right - left) // 2)], array[right])
    l = left
    r = right

    
    while True:
        
        while array[l] < pivot:
            l += 1
        while pivot < array[r]:
            r -= 1
        if (r <= l): break

        
        tmp = array[l]
        array[l] = array[r]
        array[r] = tmp
        l += 1
        r -= 1

    
    _quick_sort(array, left, l - 1)
    _quick_sort(array, r + 1, right)

def quick_sort(array):
    _quick_sort(array, 0, len(array)-1)

def median(x, y, z):
    if x < y:
        return (y if y < z else z) if x < z else x
    else:
        return (x if x < z else z) if y < z else y

n=input()
S=[]
for i in input().split():
    S.append(int(i))
S=quick_sort_(S)
word=int(int(n)/2)
s=int(S[word])-int(S[word-1])
s2=int(S[word+1])-int(S[word])
print(s)


def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr

    
    # ref = random.choice(arr)
    ref = arr[0]
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right

n=input()
S=list(input().split())
for i in S:
    i=int(i)
S=quick_sort(S)
word=int(int(n)/2)
print(S)
s=int(S[word])-int(S[word-1])
s2=int(S[word+1])-int(S[word])
print(s)


def quick_sort_with_count(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr
    ref = choice(arr)
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1

    if len(left) <= 1000:
        left = count_sort(left)
    else:
        left = quick_sort_with_count(left)

   if len(right) <= 1000:
        right = count_sort(right)
    else:
        right = quick_sort_with_count(right)

    return left + [ref] * ref_count + right
n=input()
S=[]
for i in input().split():
    S.append(int(i))
S=quick_sort_with_count(S)
word=int(int(n)/2)
s=int(S[word])-int(S[word-1])
s2=int(S[word+1])-int(S[word])
print(s)


def _quick_sort(array, left, right):
    if left >= right: return

    
    pivot = median(array[left], array[(left + (right - left) // 2)], array[right])
    l = left
    r = right

    
    while True:
        
        while array[l] < pivot:
            l += 1
        while pivot < array[r]:
            r -= 1
        if (r <= l): break

        
        tmp = array[l]
        array[l] = array[r]
        array[r] = tmp
        l += 1
        r -= 1

    
    _quick_sort(array, left, l - 1)
    _quick_sort(array, r + 1, right)

def quick_sort(array):
    _quick_sort(array, 0, len(array)-1)

def median(x, y, z):
    if x < y:
        return (y if y < z else z) if x < z else x
    else:
        return (x if x < z else z) if y < z else y

n=input()
S=[]
for i in input().split():
    S.append(int(i))
S=quick_sort(S)
word=int(int(n)/2)
s=int(S[word])-int(S[word-1])
s2=int(S[word+1])-int(S[word])
print(s)


def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr

    
    # ref = random.choice(arr)
    ref = arr[0]
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right
n=int(input())
S=list(map(int,input().split()))
S=quick_sort(S)
word=n//int(2)
s=int(S[word])-int(S[word-1])
s2=int(S[word])-int(S[word-1])
print(s)


Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted