class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        if(n < 1)return 0;
        int count = 0, len = nums.size(), i = 0;
        long hi = 0;
        while(hi < n)
        {
            if(i >= len || nums[i] > hi + 1)
            {
                ++count;
                hi = 2 * hi + 1;
            }
            else
            {
                hi = nums[i] + hi;
                ++i;
            }
        }
        return count;
    }
};