Елки палки

#include <bits/stdc++.h>
#ifdef LOCAL_FLICKY
#define DEBUG(val) std::cout << #val << " = " << val << '\n'
#else
#define DEBUG(val) {}
#endif
#define int ll
using namespace std;
using ll = long long;
using pii = std::pair<int, int>;

void fast() {
#ifdef LOCAL_FLICKY
    if (!freopen("in.txt", "r", stdin)) exit(1000 - 7);
    if (!freopen("out.txt", "w", stdout)) exit(1000 - 7);
#endif
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

#define ALL(cont) cont.begin(), cont.end()
using namespace std;

//#define MULTI_TESTS
void solve();
vector<int> trace;

signed main() {
    fast();
#ifdef MULTI_TESTS
    int t; cin >> t;
    while (t--) {
#endif
    solve();
#ifdef MULTI_TESTS
    }
#endif
}


template<typename Ty>
struct Node {
    explicit Node(Ty val) : left(nullptr), right(nullptr), val_(val), size(1) {}
    Node (Ty val, Node* l, Node* r) : val_(val), left(l), right(r), size(1 + l->size + r->size) {}
    Node *left, *right;
    Ty val_;
    int size = 0;
};

template <typename Ty>
class BST {
public:

    Node<Ty>* Next(const Ty& val) {
        Node<Ty>* current = head_, *successor = nullptr;
        while (current != nullptr) {
            if (current->val_ > val) {
                successor = current;
                current = current->left;
            }
            else {
                current = current->right;
            }
        }
        return successor;
    }

    Node<Ty>* Prev(const Ty& val) {
        Node<Ty>* current = head_, *successor = nullptr;
        while (current != nullptr) {
            if (current->val_ >= val) {
                current = current->left;
            }
            else {
                successor = current;
                current = current->right;
            }
        }
        return successor;
    }

    Node<Ty>* Minimum(Node<Ty>* node) {
        if (node->left == nullptr) {
            return node;
        }
        return Minimum(node->left);
    }

    Node<Ty>* Maximum(Node<Ty>* node) {
        if (node->right == nullptr) {
            return node;
        }
        return Maximum(node->right);
    }

    Node<Ty>* GetHead() {
        return head_;
    }

    bool Exist(const Ty& val) {
        return Find(head_, val) != nullptr;
    }

    void Delete(const Ty& val) {
        head_ = Delete(head_, val);
    }

    void Insert(const Ty& val) {
        head_ = Insert(head_, val);
    }

    void PrintPreorder(Node<Ty>* node, vector<string> pref = {}) {
        if (node != nullptr) {
            #ifdef LOCAL_FLICKY
            cout << "val: " << node->val_ << " size: " << node->size << " : ";
            for (auto e : pref) {
                cout << e;
            }
            cout << '\n';
            #endif
            if (trace.size() < pref.size() + 1) {
                trace.push_back(node->val_);
            } else {
                trace[pref.size()] = node->val_;
            }
            pref.push_back("->left ");
            PrintPreorder(node->left, pref);
            pref.pop_back();
            pref.push_back("->right ");
            PrintPreorder(node->right, pref);
            pref.pop_back();
        }
    }

    Ty KthElement(int k) {
        k = head_->size - k + 1;
        Node<Ty>* node = head_;
        while (true) {
            int size = 1;
            if (node->left != nullptr) {
                size = node->left->size + 1;
            }
            if (size == k) {
                return node->val_;
            } else if (node->left == nullptr || size < k) {
                k -= size;
                node = node->right;
            } else {
                node = node->left;
            }
        }
        exit(1);
    }

private:
    Node<Ty>* Insert(Node<Ty>* x, const Ty& z) {
        if (x == nullptr) {
            return new Node(z);
        }
        else {
            if (z < x->val_)
                x->left = Insert(x->left, z);
            else if (z > x->val_)
                x->right = Insert(x->right, z);

            x->size = 1;
            if (x->left) x->size += x->left->size;
            if (x->right) x->size += x->right->size;
        }

        return x;
    }

    Node<Ty>* Delete(Node<Ty>* root, const Ty& val) {
        if (!Exist(val)) {
            return root;
        }
        if (root == nullptr) {
            return root;
        }
        root->size -= 1;
        if (val < root->val_) {
            root->left = Delete(root->left, val);
        }
        else if (val > root->val_) {
            root->right = Delete(root->right, val);
        }
        else if (root->left != nullptr and root->right != nullptr) {
            root->val_ = Minimum(root->right)->val_;
            root->right = Delete(root->right, root->val_);
        }
        else {
            if (root->left != nullptr) {
                root = root->left;
            }
            else if (root->right != nullptr) {
                root = root->right;
            }
            else {
                root = nullptr;
            }
        }
        return root;
    }

    Node<Ty>* Find(Node<Ty>* x, const Ty& k) {
        if (x == nullptr or k == x->val_)
            return x;
        if (k < x->val_)
            return Find(x->left, k);
        else
            return Find(x->right, k);
    }

    Node<Ty>* head_ = nullptr;
};

const int inf = 1e9 + 7;

template<typename Ty>
void travel(Node<Ty>* node, vector<int>& trace, int depth = 0) {
    if (node == nullptr) {
        return;
    }
    travel(node->right, trace, depth + 1);
    travel(node->left, trace, depth + 1);
}

void solve() {
    int n; cin >> n;
    BST<int> tree;
    while (n-- > 0) {
        int v; cin >> v;
        tree.Insert(v);
        #ifdef LOCAL_FLICKY
        cout << "TREE:\n";
        tree.PrintPreorder(tree.GetHead());
        cout << "--------\n";
        cout.flush();
        #endif
    }
    tree.PrintPreorder(tree.GetHead());
    for (auto e : trace) cout << e << ' ';
}