class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l = 1, r = nums.size();
        while(l < r){
            int mid = l + r >> 1;
            int s = 0;
            for(int i = 0; i < nums.size(); i ++ ){
                if(nums[i] >= l && nums[i] <= mid)  s ++ ;
            }
            if(s > mid - l + 1) r = mid;
            else    l = mid + 1;
        }
        return l;
    }
};