#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("algsort.in");
ofstream fout("algsort.out");

inline int getRandomNumber(int lowerBound, int upperBound) {
    return lowerBound + rand() % (upperBound - lowerBound + 1);
}

class Sorter {
public:
    virtual vector<int> sort(const vector<int>& numbers) const = 0;

    virtual ~Sorter() = default;
};

class MergeSorter : public Sorter {
public:
    vector<int> sort(const vector<int>& numbers) const override {
        vector<int> sortedNumbers(numbers);
        sort(sortedNumbers, 0, (int)numbers.size() - 1);
        return sortedNumbers;
    }

private:
    void sort(vector<int>& numbers, int leftIndex, int rightIndex) const {
        // cout << leftIndex << " " << rightIndex << "\n";
        if (leftIndex >= rightIndex) {
            return;
        }

        int middleIndex = (leftIndex + rightIndex) / 2;
        sort(numbers, leftIndex, middleIndex);
        sort(numbers, middleIndex + 1, rightIndex);
        merge(numbers, leftIndex, rightIndex);
    }

    void merge(vector<int>& numbers, int leftIndex, int rightIndex) const {
        if (leftIndex >= rightIndex) {
            return;
        }

        int middleIndex = (leftIndex + rightIndex) / 2;

        vector<int> mergedValues(rightIndex - leftIndex + 1);
        int mergedValuesIndex = 0;

        int currentLeftHalfIndex = leftIndex;
        int currentRightHalfIndex = middleIndex + 1;
        while (currentLeftHalfIndex <= middleIndex && currentRightHalfIndex <= rightIndex) {
            if (numbers[currentLeftHalfIndex] <= numbers[currentRightHalfIndex]) {
                mergedValues[mergedValuesIndex++] = numbers[currentLeftHalfIndex++];
            } else {
                mergedValues[mergedValuesIndex++] = numbers[currentRightHalfIndex++];
            }
        }
        while (currentLeftHalfIndex <= middleIndex) {
            mergedValues[mergedValuesIndex++] = numbers[currentLeftHalfIndex++];
        }
        while (currentRightHalfIndex <= rightIndex) {
            mergedValues[mergedValuesIndex++] = numbers[currentRightHalfIndex++];
        }

        for (int i = leftIndex; i <= rightIndex; i++) {
            numbers[i] = mergedValues[i - leftIndex];
        }
    }
};

class QuickSorter : public Sorter {
public:
    QuickSorter() {
        srand(time(NULL));
    }

    vector<int> sort(const vector<int>& numbers) const override {
        vector<int> sortedNumbers(numbers);
        sort(sortedNumbers, 0, numbers.size() - 1);
        return sortedNumbers;
    }

private:
    inline static int nextQuartilePivot = 0;

    static int getPivotIndex(int leftIndex, int rightIndex) {
        int pivotIndex = leftIndex + (((rightIndex - leftIndex) * nextQuartilePivot) >> 2);

        nextQuartilePivot++;
        if (nextQuartilePivot == 4) {
            nextQuartilePivot = 0;
        }

        return pivotIndex;
    }

    void sort(vector<int>& numbers, int leftIndex, int rightIndex) const {
        if (leftIndex >= rightIndex) {
            return;
        }
        int pivotIndex = getPivotIndex(leftIndex, rightIndex);

        pivotIndex = arrangeNumbersAroundPivot(numbers, leftIndex, rightIndex, pivotIndex);
        
        sort(numbers, leftIndex, pivotIndex - 1);
        sort(numbers, pivotIndex + 1, rightIndex);
    }

    // Ensures all numbers before the pivot are <=pivot and all numbers after it are >=pivot
    // Returns the new pivot index
    int arrangeNumbersAroundPivot(vector<int>& numbers, int leftIndex, int rightIndex, int pivotIndex) const {
        swap(numbers[leftIndex], numbers[pivotIndex]);
        pivotIndex = leftIndex;

        int currentIndex = leftIndex + 1;
        bool treatNextEqualAsLower = true;
        while (currentIndex <= rightIndex) {
            if (numbers[currentIndex] < numbers[pivotIndex] || (numbers[currentIndex] == numbers[pivotIndex] && treatNextEqualAsLower)) {
                // We need numbers[currentIndex] before hte pivot.
                // We know that all numbers before the pivot are smaller than the pivot.
                swap(numbers[pivotIndex], numbers[pivotIndex + 1]);
                pivotIndex++;
                if (currentIndex != pivotIndex) {
                    swap(numbers[currentIndex], numbers[pivotIndex - 1]);
                }
            } else {
                currentIndex++;
            }

            if (numbers[currentIndex] == numbers[pivotIndex]) {
                treatNextEqualAsLower = !treatNextEqualAsLower;
            }
        }
        return pivotIndex;
    }
};

void sortAndPrint(const vector<int>& numbers, const Sorter& sorter) {
    vector<int> sortedNumbers = sorter.sort(numbers);
    // cout << "printing with size " << sortedNumbers.size() << "\n";
    for (int number : sortedNumbers) {
        fout << number << " ";
    }
}

int main() {
    int n;
    fin >> n;
    vector<int> numbers(n);
    for (int i = 0; i < n; i++) {
        fin >> numbers[i];
    }

    sortAndPrint(numbers, QuickSorter());

    return 0;
}