Envío 3431

Código

import random

def three_way_part(a, lo, hi):
    if hi <= lo:
        return

    lt = lo
    i = lo + 1
    gt = hi
    item = a[lo]

    while i <= gt:
        if a[i] < item:
            a[lt], a[i] = a[i], a[lt]
            lt += 1
            i += 1
        elif a[i] > item:
            a[i], a[gt] = a[gt], a[i]
            gt -= 1
        else:
            i += 1

    three_way_part(a, lo, lt - 1)
    three_way_part(a, gt + 1, hi) 



def qs(a, n):
    random.shuffle(a)
    three_way_part(a, 0, n - 1)

n = int(input())
a = [int(x) for x in input().split()]

if n > 1:
    qs(a, n)
print(*a)