#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

ifstream fin("algsort.in");
ofstream fout("algsort.out");

class ScapeGoatTree {

private:

    static const double kAlpha;
    static const int inf = (int)((1LL << 31) - 1);
    int m_maxNodeCount, m_nodeCount;

    struct Node {
        int key, size, min, max;
        Node *left, *right;
        Node(int key = -1, Node* left = nullptr, Node* right = nullptr) :
            key(key), left(left), right(right) {
            Update();
        }
        void Update() {
            min = inf, max = -1;
            if (key < 0) {
                size = 0;
                return;
            }
            size = 1, min = max = key;
            if (left) {
                size += left->size;
                min = std::min(min, left->min);
                max = std::max(max, left->max);
            }
            if (right) {
                size += right->size;
                min = std::min(min, right->min);
                max = std::max(max, right->max);
            }
        }
        bool IsScapeGoat() {
            if ((left && left->size > kAlpha*size) || (right && right->size > kAlpha*size))
                return true;
            return false;
        }
    };

    template<class Iterator>
    Node* Build(Iterator begin, Iterator end) {

        if (begin == end)
            return nullptr;

        int dim = end - begin;
        Iterator mid = begin + dim/2;

        nth_element(begin, mid, end);
        return new Node(*mid, Build(begin, mid), Build(mid + 1, end));

    }

    void Dump(Node* node, vector<int>& values) {
        if (node == nullptr)
            return;
        Dump(node->left, values);
        values.push_back(node->key);
        Dump(node->right, values);

        delete node;
    }

    Node* Balance(Node* node) {

        node->Update();
        if (node->IsScapeGoat() == false)
            return node;

        vector<int> values;
        Dump(node, values);
        return Build(values.begin(), values.end());
    }

    Node* Insert(Node* node, int key) {

        if (node == nullptr) {
            return new Node(key);
        }

        if (node->key > key)
            node->left = Insert(node->left, key);
        else
            node->right = Insert(node->right, key);

        node = Balance(node);
        return node;

    }

    Node* Erase(Node* node, int key) {

        if (node == nullptr)
            return nullptr;

        if (node->key == key) {
            if (node->left == nullptr && node->right == nullptr) {
                delete node;
                return nullptr;
            }

            int val;
            if (node->right)
                val = node->right->min;
            else
                val = node->left->max;

            auto temp = Erase(node, val);
            temp->key = val;
            temp->Update();
            return temp;
        }

        if (node->key > key)
            node->left = Erase(node->left, key);
        else
            node->right = Erase(node->right, key);

        node->Update();
        return node;

    }

    void Print(Node* node) {
        if (node == nullptr)
            return;
        Print(node->left);
        fout << node->key << ' ';
        Print(node->right);
    }

    Node* m_root;

public:

    ScapeGoatTree(vector<int> values) {
        m_root = Build(values.begin(), values.end());
    }

    void Insert(int key) {
        m_nodeCount++; m_maxNodeCount = max(m_maxNodeCount, m_nodeCount);
        m_root = Insert(m_root, key);
    }

    void Erase(int key) {
        m_root = Erase(m_root, key);
        m_nodeCount--;
        if (m_nodeCount <= kAlpha * m_maxNodeCount)
            m_root = Balance(m_root), m_maxNodeCount = m_nodeCount;
    }

    void Print() {
        Print(m_root);
    }

};
const double ScapeGoatTree::kAlpha = 0.57;

int main() {

    int n; fin >> n;
    vector<int> vals(n);

    for (auto& it : vals)
        fin >> it;

    ScapeGoatTree sgt(vals);
    sgt.Print();
    fout << '\n';

    return 0;

}

//Trust me, I'm the Doctor!