int Solve(const vector<int>& data) {
    long long lo = data.front();
    long long hi = data.back();
    long long curr_dist = 0;
    int curr_houses_num = 0;
    vector<long long> left_houses_dist;

    for (int i = lo, j = 0; i <= hi; ++i) {
        curr_dist += curr_houses_num;
        left_houses_dist.push_back(curr_dist);
        if (data[j] == i) {
            ++curr_houses_num;
            ++j;
        }
    }

    curr_dist = 0;
    curr_houses_num = 0;
    vector<long long> right_houses_dist;

    for (int i = hi, j = data.size() - 1; i >= lo; --i) {
        curr_dist += curr_houses_num;
        right_houses_dist.push_back(curr_dist);
        if (data[j] == i) {
            ++curr_houses_num;
            --j;
        }
    }

    long long smallest_dist = numeric_limits<int>::max();
    long long smallest_dist_pos = -1;
    long long N = right_houses_dist.size();
    for (auto i = 0; i < N; ++i) {
        auto curr_total_dist = left_houses_dist[i] + right_houses_dist[N - i - 1];
        if (curr_total_dist <= smallest_dist) {
            smallest_dist = curr_total_dist;
            smallest_dist_pos = lo + i;
        }
    }
    return smallest_dist_pos;
}