import random
import sys
sys.setrecursionlimit(1000000)  # allow deeper recursion if needed
 
class Solution(object):
    def sortArray(self, nums):
        self.quickSort(nums, 0, len(nums) - 1)
        return nums
 
    def quickSort(self, nums, low, high):
        if low >= high:
            return
 
        # choose random pivot and move it to the end
        pivotIndex = random.randint(low, high)
        self.swap(nums, pivotIndex, high)
        pivot = nums[high]
 
        # 3-way partition
        lt = low          # nums[low..lt-1] < pivot
        i = low           # nums[lt..i-1] == pivot
        gt = high         # nums[gt+1..high] > pivot
        while i <= gt:
            if nums[i] < pivot:
                self.swap(nums, lt, i)
                lt += 1
                i += 1
            elif nums[i] > pivot:
                self.swap(nums, i, gt)
                gt -= 1
            else:
                i += 1
 
        # recurse on < and > parts
        self.quickSort(nums, low, lt - 1)
        self.quickSort(nums, gt + 1, high)
 
    def swap(self, nums, i, j):
        nums[i], nums[j] = nums[j], nums[i]
 

aW1wb3J0IHJhbmRvbQppbXBvcnQgc3lzCnN5cy5zZXRyZWN1cnNpb25saW1pdCgxMDAwMDAwKSAgIyBhbGxvdyBkZWVwZXIgcmVjdXJzaW9uIGlmIG5lZWRlZAoKY2xhc3MgU29sdXRpb24ob2JqZWN0KToKICAgIGRlZiBzb3J0QXJyYXkoc2VsZiwgbnVtcyk6CiAgICAgICAgc2VsZi5xdWlja1NvcnQobnVtcywgMCwgbGVuKG51bXMpIC0gMSkKICAgICAgICByZXR1cm4gbnVtcwoKICAgIGRlZiBxdWlja1NvcnQoc2VsZiwgbnVtcywgbG93LCBoaWdoKToKICAgICAgICBpZiBsb3cgPj0gaGlnaDoKICAgICAgICAgICAgcmV0dXJuCgogICAgICAgICMgY2hvb3NlIHJhbmRvbSBwaXZvdCBhbmQgbW92ZSBpdCB0byB0aGUgZW5kCiAgICAgICAgcGl2b3RJbmRleCA9IHJhbmRvbS5yYW5kaW50KGxvdywgaGlnaCkKICAgICAgICBzZWxmLnN3YXAobnVtcywgcGl2b3RJbmRleCwgaGlnaCkKICAgICAgICBwaXZvdCA9IG51bXNbaGlnaF0KCiAgICAgICAgIyAzLXdheSBwYXJ0aXRpb24KICAgICAgICBsdCA9IGxvdyAgICAgICAgICAjIG51bXNbbG93Li5sdC0xXSA8IHBpdm90CiAgICAgICAgaSA9IGxvdyAgICAgICAgICAgIyBudW1zW2x0Li5pLTFdID09IHBpdm90CiAgICAgICAgZ3QgPSBoaWdoICAgICAgICAgIyBudW1zW2d0KzEuLmhpZ2hdID4gcGl2b3QKICAgICAgICB3aGlsZSBpIDw9IGd0OgogICAgICAgICAgICBpZiBudW1zW2ldIDwgcGl2b3Q6CiAgICAgICAgICAgICAgICBzZWxmLnN3YXAobnVtcywgbHQsIGkpCiAgICAgICAgICAgICAgICBsdCArPSAxCiAgICAgICAgICAgICAgICBpICs9IDEKICAgICAgICAgICAgZWxpZiBudW1zW2ldID4gcGl2b3Q6CiAgICAgICAgICAgICAgICBzZWxmLnN3YXAobnVtcywgaSwgZ3QpCiAgICAgICAgICAgICAgICBndCAtPSAxCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICBpICs9IDEKCiAgICAgICAgIyByZWN1cnNlIG9uIDwgYW5kID4gcGFydHMKICAgICAgICBzZWxmLnF1aWNrU29ydChudW1zLCBsb3csIGx0IC0gMSkKICAgICAgICBzZWxmLnF1aWNrU29ydChudW1zLCBndCArIDEsIGhpZ2gpCgogICAgZGVmIHN3YXAoc2VsZiwgbnVtcywgaSwgaik6CiAgICAgICAgbnVtc1tpXSwgbnVtc1tqXSA9IG51bXNbal0sIG51bXNbaV0K