int minCacheSize(int n, const vector<string>& reqs, int k){

    auto getHits = [&](int sz) {
        unordered_set<string> cache;
        list<string> order;
        int hits = 0;

        for (const string& item : reqs) {
            if (cache.find(item) != cache.end()) {
                hits++;
                order.erase(find(order.begin(), order.end(), item));
                order.push_front(item);
            } 
            else {
                if (cache.size() == sz) {
                    cache.erase(order.back());
                    order.pop_back();
                }
                cache.insert(item);
                order.push_front(item);
            }
        }
        return hits;
    };

    int l = 1, r = n, res = -1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (getHits(m) >= k) {
            res = m;
            r = m - 1; 
        } else {
            l = m + 1;
        }
    }

    return res;
}

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int x) : data(x), left(nullptr), right(nullptr) {}
};

int solve(Node* root, int &maxi) {
    if (root == NULL) return INT_MAX;
    
    if (root->left == NULL && root->right == NULL) return root->data;
    
    int left = solve(root->left, maxi);
    int right = solve(root->right, maxi);
    
    if (left != INT_MAX) maxi = max(maxi, root->data - left);
    if (right != INT_MAX) maxi = max(maxi, root->data - right);
    

    return min(root->data, min(left, right));
}

int maxDiff(Node* root) {
    if (root == NULL) return 0;
    
    int maxi = INT_MIN;
    solve(root, maxi);
    
    return maxi;
}

Node* buildTree(const vector<int>& levelOrder) {
    if (levelOrder.empty() || levelOrder[0] == -1) return nullptr;

    Node* root = new Node(levelOrder[0]);
    queue<Node*> q;
    q.push(root);
    int index = 1;

    while (!q.empty() && index < levelOrder.size()) {
        Node* node = q.front();
        q.pop();

        if (index < levelOrder.size() && levelOrder[index] != -1) {
            node->left = new Node(levelOrder[index]);
            q.push(node->left);
        }
        index++;

        if (index < levelOrder.size() && levelOrder[index] != -1) {
            node->right = new Node(levelOrder[index]);
            q.push(node->right);
        }
        index++;
    }

    return root;
}

int main() {
    int height;
    cin >> height;

    vector<int> levelOrder;
    int value;


    while (cin >> value) {
        levelOrder.push_back(value);
    }

    if (height == 0 levelOrder.empty() (levelOrder.size() == 1 && levelOrder[0] == -1)) {
        cout << 0 << endl;
        return 0;
    }

    Node* root = buildTree(levelOrder);
    int result = maxDiff(root);

    cout << result << endl;

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* buildTree(const vector<string>& levelOrder) {
    if (levelOrder.empty() || levelOrder[0] == "-1") return nullptr;

    TreeNode* root = new TreeNode(stoi(levelOrder[0]));
    queue<TreeNode*> q;
    q.push(root);
    int index = 1;

    while (!q.empty() && index < levelOrder.size()) {
        TreeNode* node = q.front();
        q.pop();

        if (index < levelOrder.size() && levelOrder[index] != "-1") {
            node->left = new TreeNode(stoi(levelOrder[index]));
            q.push(node->left);
        }
        index++;

        if (index < levelOrder.size() && levelOrder[index] != "-1") {
            node->right = new TreeNode(stoi(levelOrder[index]));
            q.push(node->right);
        }
        index++;
    }

    return root;
}

int sumOfNodesWithoutSiblings(TreeNode* root) {
    if (!root) return -1;

    queue<TreeNode*> q;
    q.push(root);
    int sum = 0;

    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();

        if ((node->left && !node->right) || (!node->left && node->right)) {
            sum += node->left ? node->left->val : node->right->val;
        }

        if (node->left) {
            q.push(node->left);
        }
        if (node->right) {
            q.push(node->right);
        }
    }

    return sum == 0 ? -1 : sum;
}

int main() {
    int height;
    cin >> height;
    
    vector<string> levelOrder;
    string value;

    while (cin >> value) {
        levelOrder.push_back(value);
    }

    if (height == 0 levelOrder.empty() (levelOrder.size() == 1 && levelOrder[0] == "-1")) {
        cout << -1 << endl;
        return 0;
    }

    TreeNode* root = buildTree(levelOrder);
    int result = sumOfNodesWithoutSiblings(root);
    cout << result << endl;

    return 0;
}

def get_last_animal_name_length(animal_sequence):
    animals = [animal for animal in animal_sequence.split('-') if animal != '']
    last_animal = animals[-1]
    return len(last_animal)

#include <bits/stdc++.h>
using namespace std;

class UnionFind {
    vector<int> parent, rank;
    
public:
    UnionFind(int n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        rank.resize(n, 0);
    }
    
    int find(int u) {
        if (u != parent[u])
            parent[u] = find(parent[u]);
        return parent[u];
    }
    
    void unite(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            if (rank[rootU] > rank[rootV])
                parent[rootV] = rootU;
            else if (rank[rootU] < rank[rootV])
                parent[rootU] = rootV;
            else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
        }
    }
};

int solve(int n, int c_service, int c_link, vector<pair<int, int>>& pairs) {
    UnionFind uf(n);

    for (auto& p : pairs) {
        uf.unite(p.first - 1, p.second - 1); 
    }

    vector<bool> conn(n, false);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int root = uf.find(i);
        if (!conn[root]) {
            conn[root] = true;
            cnt++;
        }
    }

    int op1 = n * c_service; 
    int op2 = cnt * c_service + (n - cnt) * c_link;

    return min(op1,op2);
}

int main() {
    int n, c_service, c_link, numPairs;
  
    cin >> n >> numPairs >> c_service >> c_link;

    vector<pair<int, int>> pairs(numPairs);

    for (int i = 0; i < numPairs; i++) {
        cin >> pairs[i].first >> pairs[i].second;
    }

    int minCost = solve(n, c_service, c_link, pairs);
    cout << minCost << endl;

    return 0;
}

#include <iostream>
using namespace std;

int solve(int a, int b) {
    long result = 1;
    long low = 1;
    long high = a;
    while (low <= high) {
        long mid = (low + high) / 2;
        if ((mid * (mid - 1)) / 2 <= b) {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

#include <bits/stdc++.h>
using namespace std;

bool canForm(int m, int k) {
    return m >= k * (k - 1);
}

int solve(int n, int m) {
    int l = 1, r = n;
    int res = 1;

    while (l <= r) {
        int mid = l + (r - l) / 2;

        if (canForm(m, mid)) {
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    return res;
}

int main() {
    int n, m;
    cin >> n >> m;

    int ans = solve(n, m);
    cout << ans<< endl;

    return 0;
}

#include <iostream>
#include <vector>
#include <deque>
#include <climits>
#include <algorithm>

int solve(int N, int K, const std::vector<int>& houses) {
    vector<int> indices(N);
    for (int i = 0; i < houses.size(); i++) {
        indices[houses[i] - 1] = i + 1;
    }

deque<int> maxDeque;
    int ans = INT_MAX;

    for (int i = 0; i < K; i++) {
        while (!maxDeque.empty() && indices[i] >= indices[maxDeque.back()]) {
            maxDeque.pop_back();
        }
        maxDeque.push_back(i);
    }

    ans = indices[maxDeque.front()];

    for (int i = K; i < N; i++) {
        if (maxDeque.front() <= i - K) {
            maxDeque.pop_front();
        }
        while (!maxDeque.empty() && indices[i] >= indices[maxDeque.back()]) {
            maxDeque.pop_back();
        }
        maxDeque.push_back(i);

        ans = std::min(ans, indices[maxDeque.front()]);
    }

    return ans;
}

def solve(N, M, K, arr):
    target_avg = K / N
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i + 1] = prefix_sum[i] + arr[i]
    
    def checkPerm():
        score = 0
        for i in range(N):
            if score / (i + 1) < target_avg:
                score += M
            elif score / (i + 1) > target_avg:
                return False
        return score / N == target_avg
    
    def averageScore(index, currSum):
        if index == N:
            return currSum == K
        
        for i in range(index, N):
            arr[index], arr[i] = arr[i], arr[index]
            if currSum + arr[index] <= K and averageScore(index + 1, currSum + arr[index]):
                return True
            arr[index], arr[i] = arr[i], arr[index]
        
        return False

    if checkPerm() or averageScore(0, 0):
        return "NO"
    return "YES"

def solve(start, stop):
    def isPerfect(num):
        original = num
        while num > 0:
            digit = num % 10
            if digit == 0 or original % digit != 0:
                return False
            num //= 10
        return True

    perfSum = 0
    for num in range(start, stop + 1):
        if isPerfect(num):
            perfSum += num
    
    return perfSum

import math

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(math.sqrt(n)) + 1):
        if primes[i]:
            for j in range(i * i, n + 1, i):
                primes[j] = False
    return primes

def least_prime_factor(n, primes):
    for i in range(2, n + 1):
        if primes[i] and n % i == 0:
            return i
    return n

def divisor_queries(N, Q, a, queries):
    max_val = max(max(a), 10**6)
    primes = sieve_of_eratosthenes(max_val)
    
    results = []
    for query in queries:
        query_type = query[0]
        
        if query_type == 1:
            l, r = query[1], query[2]
            for i in range(l - 1, r):
                lpf = least_prime_factor(a[i], primes)
                a[i] //= lpf
        
        elif query_type == 2:
            l, r = query[1], query[2]
            sum_range = sum(a[l-1:r])
            results.append(sum_range)
        
        elif query_type == 3:
            i, k = query[1], query[2]
            a[i-1] = k
    
    return results