(omg fz blog!) i guess you can binary search on a segment tree that have vec[i] as indices and 1 as value, the condition of the bs would be if(m-i+1 < query(i, m)) go left else go right, this should work, so lg^2(n) per query and lg(n) updates, if you hate segment tree (*get some help*) ig you can do prefix sum + coordinate compression but that's confusing to implement, interested if a better solution is possible!

If there are insertion, deletion operations on our vector:

Let n = upper bound on answer.

We can maintain a set of numbers not present in the given vector, let's denote it as S. Finding the answer will be the same as finding the lowest number in S, not less than X. So the time complexity will be O(nlog(n))

If there are no insertion, deletion operations on our vector:

Let's denote the given vector as v. Let's sort v and remove duplicates, and for each x in v, precalculate answer if X = x. If X is present in v, output the value that we precalculated, otherwise output X. To precalculate answer for each x in v, we can do the following: if x+1 is present in v, then answer for x will be equal to answer for x+1, otherwise x+1 will be the answer.

Time complexity will be O((q+N)log(N)), where q is the number of queries and N is the number of elements in vector.

Build a weight segment tree which records the number of the elements that do not exist in the vector, binary search on the segment tree to find the first location that its prefix sum of the number is not $$$0$$$.

The time complexity is $$$O((n+q)\log W)$$$.

subtract x from everything and deal it like mex

lets say you have 4, 5, 6, 9, 10 in your data

we will store in map {4, 6} {9, 10}

now lets say you want >= missing key for 9

so we query <= 9 which is 9 itself in the map

then the value of it is 10, hence all numbers from 9 to 10 are present so 11 is the missing one

 map<int, int> interval;
    unordered_map<int, int, chash> fmap;

    void insert(int value) {
        fmap[value]++;
        if (fmap[value] > 1) return;

        int l = floor(interval, value);
        if (l != -1 && interval[l] >= value - 1)
            interval[l] = max(interval[l], value);
        else {
            l = value;
            interval[l] = l;
        }

        if (interval.count(interval[l] + 1)) {
            int val = interval[l] + 1;
            interval[l] = interval[interval[l] + 1];
            interval.erase(val);
        }
    }

    void erase(int value) {
        fmap[value]--;
        if (fmap[value] > 0) return;

        int l = floor(interval, value);
        if (l == value) {
            interval[value + 1] = interval[l];
            interval.erase(value);
        } else {
            interval[value + 1] = interval[l];
            interval[l] = value - 1;
        }
    }

    int query(int value) {
        int f = floor(interval, value);
        if (f == -1) return value;
        return max(interval[f] + 1, value);
    }

i have created a problem on polygon refer the first question of this mashup https://codeforces.me/contestInvitation/0c55b0f44793caa990ef4f0bf1d13711ef2481d1

set mex = x, sort the vector (dont need to if its a set), then increment mex while mex is found in the vector/set