class Solution {
public:
    vector<int> duplicates(vector<int>& nums){
        unordered_set<int> uSet;
        int n = nums.size();
        vector<int> dup(n, 0);
        for(int i = 0 ; i < n ;i++){
            if(uSet.find(nums[i]) != uSet.end()){
                dup[i] = 1;
            }
            if(i != 0)
                dup[i] += dup[i-1];
            uSet.insert(nums[i]);
        }
        return dup;
    }
    int minOperations(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int req = nums.size() - 1 , ans = nums.size() - 1, n =nums.size();
        vector<int> d = duplicates(nums);
        for(int ptr = 0; ptr < n-1 ;ptr++ ){
            int idx = lower_bound(nums.begin(), nums.end(), req + nums[ptr]) - nums.begin();
            if(idx < n ){
                int val = nums[ptr] + req;
                if(nums[idx] != val)
                    ans = min(ans, n - idx + ptr + d[idx] - d[ptr]);
                else
                    ans = min(ans, n - idx + ptr - 1 + d[idx] - d[ptr]);
            } 
            else
                ans = min(ans, d[n-1] - d[ptr]+ptr);
        }
        return ans;

    }
};