#include <iostream>
#include <fstream>
#include <vector>
// #include <queue>


// _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
// _ _ _ СТРУКТУРА УЗЛА ДЕРЕВА _ _ _
// _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
struct Node {
    int key;
    Node* left = nullptr;
    Node* right = nullptr;
    Node(int key, Node* left, Node* right) {
        this->key = key;
        this->left = left;
        this->right = right;
    }
};

//_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
// _ _ _ ФУНКЦИИ ОБРАБОТКИ ВЕКТОРА И ДЕРЕВА _ _ _
//_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Node* addNode(int key, Node* left, Node* right) {
    Node* node = new Node(key, left, right);
    return node;
}


int midOfVector(int start, int end) {
    return start + (end - start) / 2;
}


Node* vectorToBST(std::vector<int> vector, int start, int end);

Node* newRoot(std::vector<int> vector, int start, int end) {
    return addNode(vector[midOfVector(start, end)],vectorToBST(vector, start, midOfVector(start, end) - 1), vectorToBST(vector, midOfVector(start, end) + 1, end));
}

void exit() { return; }

Node* vectorToBST(std::vector<int> vector, int start, int end) {
    return start > end ? nullptr : newRoot(vector, start, end);
}

//int vectorSize(vector<int> vector) {
//    return vector.size();
//}

//_ _ _ _ _ _ _ _ _ _ _ _ _ _
// _ _ _ ЧТЕНИЕ С ФАЙЛА _ _ _
//_ _ _ _ _ _ _ _ _ _ _ _ _ _
std::vector<int> readFile() {
    std::ifstream fin("input6.txt");
    std::vector<int> data;
    std::copy(std::istream_iterator<int>(fin), std::istream_iterator<int>(), std::back_inserter<std::vector<int> >(data));
    return data;
}

// _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
// _ _ _ ВЫВОД ЧЕРЕЗ DFS _ _ _
// _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
int printDFS(Node* node) {
    node == nullptr ? std::cout << "null " : std::cout << node->key << " ";
    // node == nullptr ? exit() : [](){};
    if (node == nullptr) { return 0; }
    printDFS(node->right) + printDFS(node->left);
    return 1;
}
// _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

int main(){
    std::vector<int> data = readFile();
    printDFS(vectorToBST(data, 0, data.size() - 1));
    return 0;
}