T4 TLE

class Solution {
public:
    int medianOfUniquenessArray(vector<int>& ns) {
        vector<vector<int>> pos(1e5 + 1);
        for (int i = 0; i < ns.size(); ++i) {
            pos[ns[i]].push_back(i);
        }
        function<bool(int, int, int, int, int&, int)> get_gt_kc = [&](int beg, int end, int k, int cur_k, int& got, int need) {
            if (beg + k > end) return false;
            if (cur_k < k) return false;
            ++got;
            if (got >= need) return true;

            const auto& v1 = pos[ns[beg]], &v2 = pos[ns[end - 1]];
            int i1 = upper_bound(v1.begin(), v1.end(), beg) - v1.begin();
            int i2 = upper_bound(v2.begin(), v2.end(), beg) - v2.begin();
            int opt1 = get_gt_kc(beg + 1, end, k, cur_k - (i1 >= end), got, need);
            int opt2 = get_gt_kc(beg, end - 1, k, cur_k - (i2 >= end - 1), got, need);
            return got >= need;
        };
        set<int> ss(ns.begin(), ns.end());
        int n = ns.size(), ck = ss.size();
        int lb = 0, ub = n, need = (n * (n + 1) / 2 + 1)/ 2;
        while(lb + 1 <= ub) {
            int mid = (lb + ub) / 2, got = 0;
            if (get_gt_kc(0, n, mid, ck, got, need)) {
                ub = mid;
            } else {
                lb = mid;
            }
        }
        return ub;
    }
};