Algo1

#include <bits/stdc++.h>

using namespace std;

ifstream in("in.txt");
ofstream out("out.txt");

struct compare {
    bool operator()(pair<int, int> a, pair<int, int> b) const {
        if (a.first == b.first) return a.second > b.second;
        else return a.first < b.first;
    }
};

typedef set<pair<int, int>, compare> spec_set;

spec_set leavesLeft;
spec_set leavesRight;
spec_set leavesUp;

class binary_tree {
public:

    struct node {
        node() {
            right_descendant = nullptr;
            left_descendant = nullptr;
            ancestor = nullptr;
            key = 0;
        }
        node(int newKey) {
            right_descendant = nullptr;
            left_descendant = nullptr;
            ancestor = nullptr;
            key = newKey;
        }
        node* ancestor;
        node* right_descendant;
        node* left_descendant;
        int key, heigth, way;
    };
private:
    node* tree_root;
    node* pivotal_node;
    map<int, bool> used;
public:

    binary_tree() {
        tree_root = pivotal_node = nullptr;
    }

    void add_key(int key) {
        add_to_tree(&tree_root, nullptr, key);
    }

    void build_tree() {
        build_ways(tree_root);
    }

    void print() {
        print_tree(pivotal_node);
    }

    void find_pivotal_vertex() {
        node* temp = tree_root;
        find_maxway(tree_root, &temp);
        if ((temp->way & 1) || (temp->way == 0)) {
            pivotal_node = tree_root;
            return;
        }
        int node_1, node_2;
        if(temp->left_descendant == nullptr) {
            node_1 = -1;
        } else {
            node_1 = temp->left_descendant->heigth;
        }

        if(temp->right_descendant == nullptr) {
            node_2 = -1;
        } else {
            node_2 = temp->right_descendant->heigth;
        }

        if (node_1 > node_2) {
            pivotal_node = temp->left_descendant;
            node_2++;
            node_1--;
            while (node_1 > node_2) {
                int node_3, node_4;
                if(pivotal_node->left_descendant == nullptr) {
                    node_3 = -1;
                } else {
                    node_3 = pivotal_node->left_descendant->heigth;
                }

                if(pivotal_node->right_descendant == nullptr) {
                    node_4 = -1;
                } else {
                    node_4 = pivotal_node->right_descendant->heigth;
                }

                if (node_3 >= node_4) {
                    pivotal_node = pivotal_node->left_descendant;
                } else {
                    pivotal_node = pivotal_node->right_descendant;
                }
                node_2++;
                node_1--;
            }
        } else {
            pivotal_node = temp->right_descendant;
            node_1++;
            node_2--;
            while (node_2 > node_1) {
                int node_3, node_4;
                if(pivotal_node->left_descendant == nullptr) {
                    node_3 = -1;
                } else {
                    node_3 = pivotal_node->left_descendant->heigth;
                }

                if(pivotal_node->right_descendant == nullptr) {
                    node_4 = -1;
                } else {
                    node_4 = pivotal_node->right_descendant->heigth;
                }

                if (node_3 >= node_4) {
                    pivotal_node = pivotal_node->left_descendant;
                } else {
                    pivotal_node = pivotal_node->right_descendant;
                }
                node_1++;
                node_2--;
            }
        }
        rotate_tree();
    }

private:

    void add_to_tree(node** ptr, node* temp_ancestor, int value) {
        if (*ptr == nullptr) {
            *ptr = new node(value);
            (*ptr)->ancestor = temp_ancestor;
            return;
        }
        if (value < (*ptr)->key) {
            add_to_tree(&((*ptr)->left_descendant), *ptr, value);
        } else if (value > (*ptr)->key) {
            add_to_tree(&((*ptr)->right_descendant), *ptr, value);
        }
    }

    void build_ways(node* ptr) {
        if (ptr == nullptr) return;
        build_ways(ptr->left_descendant);
        build_ways(ptr->right_descendant);
        int left_height = -1, right_height = -1;
        if (ptr->left_descendant != nullptr) {
            left_height = ptr->left_descendant->heigth;
        }
        if (ptr->right_descendant != nullptr) {
            right_height = ptr->right_descendant->heigth;
        }
        int min_h(left_height < right_height ? left_height : right_height);
        int max_h(left_height > right_height ? left_height : right_height);

        ptr->heigth = max_h + 1;
        if (min_h == -1) {
            ptr->way = max_h + 1;
        } else {
            if (left_height == right_height) {
                ptr->way = left_height + right_height + 1;
            } else {
                ptr->way = left_height + right_height + 2;
            }
        }
    }

    void print_tree(node* ptr) {
        if (ptr != nullptr) {
            out << ptr->key << endl;
            print_tree(ptr->left_descendant);
            print_tree(ptr->right_descendant);
        }
    }

    void find_maxway(node* ptr, node** max_way) {
        if (ptr != nullptr) {
            find_maxway(ptr->left_descendant, &(*max_way));
            if (ptr->way > (*max_way)->way)
                *max_way = ptr;
            find_maxway(ptr->right_descendant, &(*max_way));
        }
    }

    void rotate_tree() {
        node *temp = pivotal_node;
        while (temp->ancestor != nullptr) {
            node* parent = temp->ancestor;
            node* parent2 = parent->ancestor;
            if (temp->key > temp->ancestor->key) {
                parent->right_descendant = temp->left_descendant;
                parent->ancestor = temp;
                temp->left_descendant = parent;
                temp->ancestor = parent2;
            } else {
                parent->left_descendant = temp->right_descendant;
                parent->ancestor = temp;
                temp->right_descendant = parent;
                temp->ancestor = parent2;

            }
        }
    }

    void set_pivatal_node(node *ptr, int value) {
        if (ptr != nullptr) {
            if (ptr->key == value) {
                pivotal_node = ptr;
            } else {
                set_pivatal_node(ptr->left_descendant, value);
                set_pivatal_node(ptr->right_descendant, value);
            }
        }
    }
public:

    void get_tips() {
        node *root = pivotal_node;
        used[root->key] = true;
        find_tips(root->left_descendant, leavesLeft);
        find_tips(root->right_descendant, leavesRight);
        find_tips(root->ancestor, leavesUp);
    }

    void find_tips(node *root, spec_set &v, int cur_level = 0) {
        if(root == nullptr) return;
        if (used[root->key]) return;
        used[root->key] = true;
        if((root->left_descendant == nullptr && root->right_descendant == nullptr)
             || (root->left_descendant == nullptr && root->ancestor == nullptr)
             || (root->ancestor == nullptr && root->right_descendant == nullptr))
        {
            v.insert(make_pair(cur_level, root->key));
            return;
        }
        if (root->left_descendant != nullptr)
            find_tips(root->left_descendant, v, cur_level + 1);
        if (root->right_descendant != nullptr)
            find_tips(root->right_descendant, v, cur_level + 1);
        if (root->ancestor != nullptr)
            find_tips(root->ancestor, v, cur_level + 1);
    }

    void set_node(int value) {
        node *node = tree_root;
        set_pivatal_node(node, value);
    }

    int get_pivotal_key() {
        return pivotal_node->key;
    }
};

binary_tree tree;
binary_tree cpy;

void input() {
    int key;
    while (in >> key) {
        tree.add_key(key);
        cpy.add_key(key);
    }
}

void solve() {
    tree.build_tree();
    tree.find_pivotal_vertex();
    int key = tree.get_pivotal_key();
    cpy.set_node(key);
    cpy.get_tips();
}

void output() {
    map<int, set<int> > answer;
    int prev_key = INT_MIN;
    set<pair<int, int>>::reverse_iterator it;
    for(it = leavesLeft.rbegin(); it != leavesLeft.rend(); ++it) {
        int key = it->first;
        int value = it->second;
        if (prev_key == key) continue;
        prev_key = key;
        answer[key].insert(value);
    }
    prev_key = INT_MIN;
    for (it = leavesRight.rbegin(); it != leavesRight.rend(); ++it) {
        int key = it->first;
        int value = it->second;
        if (prev_key == key) continue;
        prev_key = key;
        answer[key].insert(value);
    }
    prev_key = INT_MIN;
    for (it = leavesUp.rbegin(); it != leavesUp.rend(); ++it) {
        int key = it->first;
        int value = it->second;
        if (prev_key == key) continue;
        prev_key = key;
        answer[key].insert(value);
    }
    for (map<int, set<int>>::reverse_iterator it = answer.rbegin(); it != answer.rend(); ++it) {
        pair<int, set<int>> p = *it;
        if (p.second.size() < 2) continue;
        set<int> s = p.second;
        long long ans = *p.second.begin() + *++p.second.begin();
        out << ans << endl;
        break;
    }
    tree.print();
}

int main() {
    input();
    solve();
    output();
}